BRS compactness

Sat Aug 9 13:46:31 EDT 2003

Dear Colleagues,

Gene Garfield asked me to put this on the list. I hope it is useful for some
of you.

Best regards,

Ronald Rousseau

***********************************************************************
BRS-compactness in networks: Theoretical considerations related to cohesion in
citation graphs, collaboration networks and the internet

Mathematical and Computer Modelling
Volume 37, Issues 7-8 , April 2003 , Pages 879-899

L. Egghe and R. Rousseau

Abstract
Compactness as introduced by Botafogo, Rivlin and Shneiderman, in short: BRS-
compactness, is studied in general, as it can be used to describe the cohesion
of parts of the internet or collaboration networks, and in the particular case
of a unidirectional network, such as a citation graph. It is shown that the
connection coefficient is an upper bound for the BRS-compactness value of a
network. During our investigations, we derive an upper bound for the
generalized Wiener index of a directed graph. Several networks are constructed
and their BRS-compactness values are calculated.

Author Keywords: BRS-compactness; Networks; Hyperlinks; Internet; Citation
networks; Collaboration graphs; Generalized Wiener index; Sum of distances in
a graph

References
1. J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins, The
web as a graph: Measurements, models, and methods. In: Proceedings of the
Fifth Annual International Computing and Combinatorics Conference (1999).
2. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A.
Tomkins and J. Wiener, Graph structure in the web. In: Proceedings of the 9th
International World Wide Web Conference (2000).
3. R.A. Botafogo, E. Rivlin and B. Shneiderman, Structural analysis of
hypertexts: Identifying hierarchies and useful metrics. ACM Transactions on
Information Systems 10 (1992), pp. 142–180
4. S. Johnson, Control for hypertext construction. Communications of the ACM
38 8 (1995), p. 87.
5. J. de Vocht, Experiments for the characterization of hypertext structures.
In: Masters Thesis, Eindhoven University of Technology (1994).
6. E. Rivlin, R. Botafogo and B. Shneiderman, Navigating in hyperspace:
Designing a structure-based toolbox. Communications of the ACM 37 2 (1994),
pp. 87–96.
7. G. Salton, J. Allan and C. Buckley, Automatic structuring and retrieval of
large text files. Communications of the ACM 37 2 (1994), pp. 97–108.
8. L. Calvi and P. de Bra, Using dynamic hypertext to create multi-purpose
textbooks. In: Proceedings of ED-MEDIA 97 (1997).
9. E. Mendes, W. Hall and R. Harrison, Applying metrics to the evaluation of
educational hypermedia applications. Journal of Universal Computer Science 4
(1998)
10. K. Khan and C. Locatis, Searching through cyberspace: The effects of link
display and link density on information retrieval from hypertext on the world
wide web. Journal of the American Society for Information Science 49 (1998),
pp. 176–182.
11. G.H. Leazer and J. Furner, Topological indices of textual identity
networks. In: L. Woods, Editor, Proceedings of the 62nd Annual Meeting of the
American Society for Information Science, Knowledge: Creation, Organization
and Use, Information Today, Medford, NJ (1999), pp. 345–358.
12. M. Randi , On characterization of molecular branching. Journal of the
American Chemical Society 97 (1975), pp. 6609–6615.
13. D.J. de Solla Price, Networks of scientific papers. Science 149 (1965),
pp. 510–515.
14. M.A. Shepherd, C.R. Watters and Y. Cai, Transient hypergraphs for citation
networks. Information Processing and Management 26 (1990), pp. 395–412
15. A. Pritchard, On the structure of information transfer networks. In: M.
Phil. Thesis, School of Librarianship, Polytechnic of North London (1984).
16. Y. Ding, S. Foo and G. Chowdhury, A bibliometric analysis of collaboration
in the field of information retrieval. International Information and Library
Review 30 (1998), pp. 367–376.
17. H. Kretschmer, Types of two-dimensional and three-dimensional
collaboration patterns. In: C. Macias-Chapula, Editor, Proceedings of the
Seventh Conference of the International Society for Scientometrics and
Informetrics, Universidad de Colima, Mexico (1999), pp. 244–266.
18. A.L. Barabasi and R. Albert, Emergence of scaling in random networks.
Science 286 (1999), pp. 509–512
19. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan,
S. Rajagopalan and A. Tomkins, Hypersearching the web. Scientific American 280
6 (1999), pp. 54–60.
20. S. Brin and L. Page, Anatomy of a large-scale hypertextual web-search
engine. In: Proceedings of the 7th International World Wide Web Conference
(1998), pp. 107–117 Brisbane, Australia .
21. M.R. Henzinger, Hyperlink analysis for the web. IEEE Internet Computing 5
1 (2001), pp. 45–50
22. G. Pinski and F. Narin, Citation influences for journal aggregates of
scientific publications: Theory, with applications to the literature of
physics. Information Processing and Management 12 (1976), pp. 297–312
23. N. Geller, On the citation influence methodology of Pinski and Narin.
Information Processing and Management 14 (1978), pp. 93–95
24. J. Kleinberg, Authoritative sources in a hyperlinked environment. Journal
of the ACM 46 5 (1999), pp. 604–632.
25. P. de Bra, Using hypertext metrics to measure research output levels.
Scientometrics 47 (2000), pp. 227–236
26. D. Knuth. In: The Art of Computer Programming, Volume 1. Fundamental
Algorithms, Addison-Wesley, Reading, MA (1969).
27. W.K. Chen, Applied Graph Theory. , North-Holland, Amsterdam (1971).
28. R.J. Wilson, Introduction to Graph Theory. , Longman, London (1972).
29. M.E.J. Newman, The structure of scientific collaboration networks. In:
Proceedings of the National Academy of Science 98 (2001), pp. 404–409 (2) .
30. C. Berge, Théorie des Graphes et ses Applications. , Dunod, Paris (1967).
31. A. Gibbons, Algorithmic Graph Theory. , Cambridge University Press,
Cambridge, UK (1985).
32. F. Harary, Graph Theory. , Addison-Wesley, Reading, MA (1969).
33. N. Trinajsti , Chemical Graph Theory. , CRC Press, Boca Raton, FL (1992).
34. H. Wiener, Structural determination of paraffin boiling points. Journal of
the American Chemical Society 69 (1947), pp. 17–20.
35. Y.W. Kim and J.H. Kim, A model of knowledge based information retrieval
with hierarchical concept graph. Journal of Documentation 46 (1990), pp. 113–
136.
36. J. Plesnik, On the sum of all distances in a graph or digraph. Journal of
Graph Theory 8 (1984), pp. 1–21.
37. R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs.
Czechoslovak Mathematical Journal 26 (1976), pp. 283–296.
38. C.P. Ng and H.H. Teh, On finite graphs of diameter 2. Nanta Mathematica 1
(1966), pp. 72–75.
39. J.K. Doyle and J.E. Graver, Mean distance in a graph. Discrete Mathematics
17 (1977), pp. 147–154.
40. Y. Fang and R. Rousseau, Lattices in citation networks: An investigation
into the structure of citation graphs. Scientometrics 50 2 (2001), pp. 273–
287.
41. I. Gutman and O. Polansky, Mathematical Concepts in Organic Chemistry. ,
Springer-Verlag, Berlin (1986).
42. D.H. Rouvray, Predicting chemistry from topology. Scientific American 255
3 (1986), pp. 36–43.
43. L. Egghe and R. Rousseau, A measure for the cohesion of weighted networks.
Journal of the Americana Society for Information Science and Technology 54 3
(2003), pp. 193–202

*************************************************************************
Ronald Rousseau
International Program Chair, 9th ISSI Conference - Beijing
KHBO - Industrial Sciences and Technology
Zeedijk 101    B-8400  Oostende   Belgium
Guest Professor at the Library of the Chinese Academy of Sciences
Honorary Professor Henan Normal University (Xinxiang, China)
E-mail: ronald.rousseau at khbo.be
web page:  users.pandora.be/ronald.rousseau

-------------------------------------------
| Please visit www.cscd.ac.cn/issi2003     |
| the site of the Beijing ISSI conference  |
===========================================