IRLS614 Outline.

Readings

There are two set texts for this course. (They are inexpensive, and readily available from Amazon and other similar sources.)

• Barabasi, A.-L. ,[2002]. Linked, Cambridge: Perseus, 2002. ISBN 0-7382- 0667-9
• Watts, Duncan J. [2003] Six degrees: The science of a connected age. ISBN 0-393- 04142-5

See also

• The study of self organized networks (Barabasi's home department at Notre Dame) and Self Organized Networks: Papers
• Barabasi, A.-L. ,[2001]. The physics of the Web
• Complex Interactive Networks Bibliography [2000]
• A. Broder et al. Graph structure in the web. (Read this as we get near the end of the course)
• Jon Kleinberg
• Jon Kleinberg [2002], The Structure of Information Networks (check the bibliography in this).
• J. Kleinberg, S. Lawrence[2001] The Structure of the Web. Science 294(2001), 1849 available from Jon Kleinberg
• Mark Newman
• Topology project This is on the structure of the Web.
• W3C A Little History of the World Wide Web: from 1945 to 1995
• Vladimir Batagelj Graph Theory and Network Analysis

Other helpful readings include

• Watts, Duncan J. [1999] Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press. This is an impressive and contentful book from one of the leaders of the discipine, but it may be a bit much for us for present purposes.

Use Sabio Information Gateway, and use the databases (you'll find this easier if you have done Research Instruction Online).

Some of the papers you may encounter elsewhere will be online in the form of Postscript (.ps)-- the instruction language for laser printers-- you'll probably need a viewer to read these, try Ghostscript etc.

The Topics

1: Introduction

Aims and objectives of course.

Readings

• Barabasi [2002] chapter 1, and glance at MafiaBoy  

2. Elementary graph theory

Graphs, directed graphs, loop graphs, isomorphic graphs, regular graphs, networks, walks, trails, paths, connected graphs, circuits, cycles, cut-vertices, bridges, trees, forests, bi-partite networks, etc.

Readings

• Graphs and Graph Theory (aimed at elementary school children), has simple depictions of edge, vertex, degree, size, regular, path , circuit, cycle , hamiltonian, eulerian, planar, non-planar, distance, diameter, isomorphic, complete, neighbor , dominating set
• Chris K. Coldwell [1995], Introduction to Graph Theory
• Graph Theory: An Introduction (look through the beginner bit)
• Gary Chartrand [1977], Introduction to Graph Theory. Dover

3: Social networks: I:

The elementary theory of social networks. Global, local and individual analyses.

Readings

• Laura Garton, Caroline Haythornthwaite, Barry Wellman [1997] Studying Online Social Networks
• Malcolm Gladwell, The Tipping Point: How Little Things Can Make a Big Difference
• Inflow
• International Network for Social Network Analysis
• Valdis Krebs[2002], Introduction to Social Network Analysis
• Valdis Krebs[1998], Knowledge Networks: Mapping and Measuring Knowledge Creation
• Peter Morville [2002] Social Network Analysis
• Social Network Analysis Instructional Web Site

4: Social networks: II:

Empirical method. Some empirical results and examples

Readings

5: Regular networks, random networks, and biased random networks

Theory of regular networks. Distribution of degrees, connectedness, diameter, and clustering in regular (nearest neighbour) networks.

Theory of random networks. Distribution of degrees, connectedness, diameter, and clustering in random networks.

Scale

Readings

• The Poisson distribution Run the applet. Don't worry about the formulas. Set repetitions to 100, and see what you get.
• Watts, Duncan J. [2003] Six degrees
• D J Watts and S H Strogatz [1998] Collective dynamics of "small-world" networks Nature (393) 440-442. access through UofA library [worm, power grid. actors] Bit advanced at this stage, but we will need this later

Harder

• M.E.J. Newman, D.J. Watts, and S.H.Strogatz [2001] Random graph models of social networks  
• Mark Newman

Too hard for us

• Bollobas B., 2001, Random Graphs Too hard for us. And Bela Bollobas
• Jon Kleinberg [2002], The Structure of Information Networks (check the bibliography in this-- most of it will be a bit hard for us).

6: Three examples of networks from the real world

Distribution of degrees (in regular graphs, in random graphs, in reality). Exponential laws, power laws and log-log plots.

Brief discussion of World Wide Web, the machine topology (routers and domains) of the Internet, chemical reactions in cells

They are not random.

Readings

• Barabasi, A.-L. ,[2002]. Linked pp67-71
• Exponential growth and decay This may be a bit much for us.
• Lada A. Adamic [2000] Zipf, Power-laws, and Pareto - a ranking tutorial This may be a bit much for us.
• Barabasi, A.-L. ,[2001]. The physics of the Web
• Equations of straight lines on various graph papers This is really good to remind you of power laws and log-log plots. But it may be a bit much if the material is entirely new to you.
• Brian Hayes [2000] Computing Science: Graph Theory in Practice: Part I This is about our level and good on the structure of the Web.
• Brian Hayes [2000] Computing Science: Graph Theory in Practice: Part II Explains exponential and power laws.

• S Lawrence and C L Giles 1999 Accessibility of information on the Web Nature 400 107 Size of Web, access through UofA library
•  A. Broder et al. [2000] Graph structure in the web [There is more in this than we need here and now, but it will be useful later.]

• M Faloutsos, P Faloutsos and C Faloutsos [1999] On power-law relationships of the Internet topology ACM SIGCOMM 99, comp. Comm. Rev. 29 251 [Domains and routers]

• H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.-L. Barabási The large-scale organization of metabolic networks, Nature 407, 651-654 (2000). Available from Self Organized Networks: Papers

7: Degrees of separation

Milgram and six degrees. Degrees of separation on the Web (Barabasi, robust). Scientific co-authorship networks (Newman, robust).

Readings

• R. Solomonoff and A. Rapaport [1951], 'Connectivity of Random Nets', Bulletin of Mathematical Biophysics 13, (1951) pp.107-117 http://world.std.com/~rjs/ray.html (but does not have download). This is the theoretical background-- we probably do not need it.

• Milgram, Stanley. "The Small World Problem." Psychology Today, 2 May 1967. pp 60 - 67.
• Judith S. Kleinfeld [2002] Could it be a big world after all? The "Six Degrees of Separation Myth".
• Judith S. Kleinfeld [2002b], 'The Small World Problem', Society 39 (2002), pp.61-66.
• Small Worlds Research Project

• R. Albert, H.Jeong, and A.-L. Barabasi [1999], 'Diameter of the World Wide Web', Nature 401 (1999) pp.107-109 Available from Self Organized Networks: Papers

• M.E.J.Newman [2000a], 'Who is the Best Connected Scientist? A Study of Scientific Coauthorship Networks',
• M.E.J.Newman [2000b], The Structure of Scientific Collaboration Networks
• M.E.J.Newman [2001] Ego-centered networks and the ripple effect&emdash; or&emdash;Why all your friends are weird. Available from Mark Newman

8: More elementary graph theory and Kleinberg's search problem

Trees, economy trees, and the minimal connector problem. Reachability and geodesic distance.

Program Evaluation and Review Technique (P.E.R.T. charts) and Critical Path analysis

Finding short paths.

Readings

• Graphs and Graph Theory (aimed at elementary school children), has simple depictions of edge, vertex, degree, size, regular, path , circuit, cycle , hamiltonian, eulerian, planar, non-planar, distance, diameter, isomorphic, complete, neighbor , dominating set
• Chris K. Coldwell [1995], Introduction to Graph Theory
• Graph Theory: An Introduction (look through the beginner bit)
• Gary Chartrand [1977], Introduction to Graph Theory. Dover

• J.J.Kleinberg [1999] The Small-World Phenomenon: An Algorithmic Perspective and his[2000], 'Navigation in a Small World--It is easier to find short chains between points in some networks than in others', Nature 406 (2000) p.845 available from Jon Kleinberg. The original, and longer, paper is clearer, having details useful to us
• Watts, Duncan J. [2003] Six degrees
• Watts, D.J., Dodds, P.S., and Newman, M.E.J. [2002] Identity and search in social networks. Science, 296, 1302-1305 (2002). available from Mark Newman [This may be a little bit difficult for us, but it does explain the problem and offers a solution.]

9: Small worlds and their models

Small worlds. Granovetter. Clustering coefficient. Cavemen and solarians. The random, Watts and Strogatz, hubs, power law, and Kleinberg models.

Readings

• Mark S. Granovetter [1973], 'The Strength of Weak Ties', American Journal of Sociology 78, (1973) pp.1360-1380.
• Newman, M. E. J. [2000] Models of the Small World: A Review.
• D. J. Watts, [1999] Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press
• Small Worlds Research Project

• D J Watts and S H Strogatz 1998 Collective dynamics of "small-world" networks Nature (393) 440-442 , access through UofA library [worm, power grid. actors]
•  
• M.E.J. Newman, D.J. Watts, and S.H.Strogatz [2001] Random graph models of social networks  
• Mark Newman
•  
• Amaral, L. A. N., Scala, A., Barthelemy, M., and Stanley, H. E.[2000] Classes of behavior of small-world networks.
•  

10: Hubs, Connectors, and Scale free networks

Bacon, Erdos, etc. Power law. Scale-free networks.

Readings

• Malcom Gladwell [2000], The Tipping Point http://www.gladwell.com/books2.html
• Emanuel Rosen [2000], The Anatomy of Buzz http://www.emanuel-rosen.com/

• Brian Hayes [2000] Computing Science: Graph Theory in Practice: Part II Explains exponential and power laws.

• Barabási, Albert-László, and Réka Albert. 1999. Emergence of scaling in random networks. Science 286:509-512.
• B. A. Huberman and L. A. Adamic, Nature 401, 131 (1999) (different model)

11: The evolution of Scale free networks

Readings

• Barabasi
• David Pennock, Gary Flake, Steve Lawrence, Eric Glover, C. Lee Giles [2002]Winners don't take all: Characterizing the competition for links on the web

12: Bibliometrics and Informetrics

Readings

Probably look at this first

• The ISI Essays

Then

• Bibliometrics Winterghager
• Christine L. Borgman and Jonathan Furner [2002] Scholarly Communication and Bibliometrics Annual Review of Information Science and Technology: Vol. 36, (ed. B. Cronin).
• Simpson, I. (1988). Bibliometrics, (look for irls506 and use the password spring506) in Basic Statistics for Librarians, 3rd ed. 177-192. London: Lib Assn.

And for citation analysis

Have a look at

• The Institute for Scientific Information Garfield is the big name here in bibliometrics (actually he was on campus a couple of years ago), and this is one of his domains.The Institute for Scientific Information produce the best known citation indices Science Citation Index (SCI), Social Sciences Citation Index (SSCI), Arts and Humanities Citation Index (A&HCI) (and SciSearch, Social SciSearch, Arts & Humanities Search).
• Smith, Linda (1981), Citation Analysis, Library Trends, Summer 1991, 9-20.

Read

• Heinz Hauffe: Is Citation Analysis a Tool for Evaluation of Scientific Contributions?
• Validation of Citation Analysis

Scan

Alfred James Lotka

13: Search engine technologies

Four continents of the Web. Search engines. Page rank. HITS. CLEVER.

Readings

• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, [1999], Hypersearching the Web. Scientific American, June 1999 This is on authorities and hubs.
• Steve Lawrence and C.Lee Giles [1998], 'Searching the World Wide Web', Science 280, (1998) pp.98-100. (Old, now, but interesting.)
• Tips for searching the Web
• Brin, S. and Page, L. [1998, 2000]. The Anatomy of a large scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7), 107-117. http://www-db.stanford.edu/~backrub/google.html about 2000
• Monika Henzinger [2000], Link Analysis in Web Information Retrieval, IEEE Data Engineering Bulletin, 23(3):3-8, 2000. and

14: Experts and authorities

Centrality, power

Readings

• J.J.Kleinberg [1999], 'Authoritative Sources in a Hyperlinked Environment', Journal of the ACM 46 (1999) p.604-632

15: Search engine technology

Readings

16: Informetrics