The complete body below was extracted in page and column order from the supplied PDF. Figure and table renderings are retained after the transcription.

Small-World Linkage and Co-Linkage

Lennart Björneborn

Royal School of Library and Information Science, Denmark

E-mail: lb@db.dk

ABSTRACT The paper presents ideas from a current research project concerned with link structures and small-world phenom- ena on the WWW, with possible implications for knowl- edge discovery or ‘web mining’. The project includes case studies of so-called co-linkage chains consisting of co- linking and co-linked web nodes (analogous to biblio- graphic couplings and co-citations) in a context of re- searchers’ homepages and published bookmark lists. Key concepts are so-called transversal links and transversal co- linkages (on co-linkage chains) functioning as short cuts or ‘weak ties’ between heterogeneous subject domains and interest communities on the Web. According to a hypothe- sis in the project, transversal links make the Web more strongly connected and ‘crumpled up’ by creating small- world phenomena in the shape of short distances between nodes in the Web graph.

KEYWORDS: WWW, link structure analysis, citation analysis, transversal links, co-linkage chains, small-world phenomena, knowledge discovery, web mining

INTRODUCTION The Web may be conceived as an ecological system [e.g., 7], that is self-organised and multi-agent constructed by millions of laymen, researchers, institutions, companies, etc., that dynamically create, adapt and remove web pages and links. The local ‘anarchistic’ behaviour of these diverse web ‘weavers’ is usually considered to have negative consequences on the global performance of the Web as a hypertext system. But so-called transversal links [2] functioning as short cuts or ‘weak ties’ between heterogeneous subject domains and interest communities may be a usable feature of this ‘imperfect’ behaviour, with possible implications for knowledge discovery or ‘web mining’ [5]. This and other ideas presented in the paper stem from a current research project concerned with link structures and small-world phenomena [11] on the Web, drawing on graph theory and bibliometric cita- tion analysis [2].

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. HT'01 8/01 Aarhus, Denmark ® 2001 ACM ISBN 1-59113-420-7/01/0008…$5.00

133

133

TRANSVERSAL LINKS By connecting heterogeneous subject domains on the Web, transversal links may affect possibilities for human serendipity and computer-supported knowledge discov- ery, when unexpected but potentially useful information is encountered and extracted. The idea of transversal links is inspired by Bush’s [4] vision of ‘Memex’ with associa- tive ‘trails’ that interlink text paragraphs, e.g., trans- versely to classificational hierarchies with implications for scientific innovativeness. A human or digital agent traversing the Web by following links from web page to web page has the possibility to move from one subject domain (e.g., in information science) to another ‘distant’ domain (e.g., in creativity research) using a single trans- versal link (e.g., on a researcher’s published bookmark list) as a short cut. According to a hypothesis in the pro- ject, transversal links make the Web more strongly con- nected and ‘crumpled up’ by creating small-world phe- nomena in the shape of short distances between nodes in the Web graph. Transversal links thus give a new signifi- cance to the social network analytic notion of ‘the strength of weak ties’ [6].

SMALL-WORLD PHENOMENA In graph theoretic terms so-called small-world networks [11] have highly clustered nodes as in regular graphs, yet characteristic path lengths between pairs of nodes are short as in random graphs. In a small-world network it is sufficient with a very small percentage of edges function- ing as short cuts (i.e. ‘transversal links’) connecting ‘dis- tant’ nodes of the network. Small-world phenomena oc- cur in a wide variety of biological, technological and social networks [11]. There is still a lack of research on small-world phenomena and their possible usabilities regarding different types of nodes and edges in informa- tional networks such as the Web [1,2], bibliographic [8] and citation databases, semantic networks, thesauri, etc. In this context, the research project is concerned with developing methods to identify and locate two different types of transversal edges on the Web: (1) on directed link paths, (2) on so-called co-linkage chains consisting of co-linking and co-linked nodes (analogous to biblio- graphic couplings and co-citations, cf. fig. 1).

LINK PATHS AND CO-LINKAGE CHAINS One way of locating transversal links on link paths be- tween web pages would be to use large-scale link struc- ture data (as in the Connectivity Server [3]) and select

start and end web pages from two heterogeneous scien- tific domains, and then identify transversal links on the shortest link path (if any [3]) connecting the web pages. Large-scale data is essential since the exclusion of rela- tively few transversal links may affect the size of strongly connected components in the Web graph. In the research project efforts are made to establish access to such large- scale link structure data.

The second type of transversal edges, in co-linkage chains, is inspired by research on literature-based knowl- edge discovery using so-called ‘indirect multi-step co- citations’ [9] (named ‘co-citation chains’ in the project) between different scientific fields to handle ‘undiscov- ered public knowledge’ [10]. Using fig. 1 on this ap- proach: If literature in scientific domain C1 is never co- cited directly with literature Cn, then literatures C2-… transitively connecting C1 to Cn may reveal implicit rela- tionships or patterns between ideas and concepts not considered before.

B1

B2 ... Bm

bibliographic coupling

link

co-citation

= same inlinks

C1 C2 C3 … Cn

Figure 1: Co-linkage chain

In the project case studies comprise co-linkage chains consisting of co-linked (co-cited) researchers’ homepages and co-linking (bibliographically coupled) bookmark lists (and similar types of ‘hotlists’), the Cs and Bs respec- tively in fig. 1. Published bookmark lists are of special interest, since their diverse contents may provide trans- versal relations on link paths and co-linkage chains be- tween heterogeneous subject domains. Bookmark lists reflect trails of varied interests, preferences and actions on the Web, and thus constitute an obvious area for scien- tometric and webometric investigation [2]. Some of the links on such lists may reflect emerging cross- disciplinary ‘research fronts’ or ‘invisible colleges’ in the evolving interconnectedness of science.

The case studies include, e.g., a co-linkage chain of 5 co- linked and 4 co-linking nodes with research interests ranging from small-world networks to distributed knowl- edge systems, interdisciplinary studies, philosophy of mind, education research, and linguistics. Co-linkage chains are constructed by alternate steps (C1, B1, C2, B2, C3, etc.) of selecting a researcher’s bookmark list with outlinks to other researchers’ homepages, and selecting a researcher’s homepage with inlinks from other research- ers’ bookmark lists. Inlink analysis is conducted using AltaVista’s advanced search features, with inherent bias of search engine coverage, performance, etc. [2]. Assess- ing heterogeneity between researchers’ scientific domains

134

134

is necessary in order to identify transversal co-linkages (as ‘weak ties’ contrary to the strong co-citations in [9]) between co-linking or co-linked nodes. This is not un- complicated. Endeavours are made to establish criteria of definition, e.g., by using low co-linkage frequency com- pared with low co-citation frequency in citation data- bases.

CONCLUDING REMARKS The presented ideas from the research project indicate complementarities between ‘convergent’ and ‘divergent’ link structures on the Web, with subject-specific domains and interest communities (‘web clusters’) corresponding to the former type and transversal links and co-linkages to the latter. These different link structures may support exploration of the Web conducted in convergent (i.e. rational, goal-directed) ways complemented by divergent (i.e. intuitive, serendipitous) behaviour. Investigating such complementarities might give a better understanding of the complex topologies, functionalities and potentials of the Web, which might be utilised in web mining, har- vesting schemes of web robots, ranking algorithms of search engines, visualisation/navigation features of browsers, etc.

REFERENCES

Adamic, L. The Small World Web. Lecture Notes in

Computer Science, 1696, (1999), 443-452.

Björneborn, L. & Ingwersen, P. Perspectives of

Webometrics. Scientometrics, 50, 1 (2001), 65-82.

Broder, A. et al. Graph Structure in the Web.

Computer Networks, 33, (2000), 309-320

Bush, V. As We May Think. The Atlantic Monthly,

(July, 1945), 101-108.

Chakrabarti, S. et al. Mining the Web’s Link Structure.

IEEE Computer, 32, 8 (1999), 60-67.

Granovetter, M.S. The Strength of Weak Ties. Ameri-

can Journal of Sociology, 78, 6 (1973), 1360-1380.

Huberman, B.A. & Adamic, L. Growth Dynamics of

the World-Wide Web. Nature, 401 (Sep 9, 1999), 131.

Newman, M.E.J. The Structure of Scientific Collabo-

ration Networks. PNAS, 98, 2 (2001), 404-409.

Small, H. A Passage Through Science: Crossing Dis-

ciplinary Boundaries. Library Trends, 48, 1 (1999), 72-108.

Swanson, D.R. Undiscovered Public Knowledge.

Library Quarterly, 56, 2 (1986), 103-118.

Watts, D. J. & Strogatz, S.H. Collective Dynamics of

‘Small-World’ Networks. Nature, 393 (June 4, 1998), 440-442.

Figure 1: Co-linkage chain