Seminar on Information Networks

Overview

CS 785 is a seminar-style course in which students will read and present papers on current research in large-scale social and information networks. Some of the main topics include link analysis, Web search, computational social network analysis, decentralized network algorithms, properties of random graphs, and probabilistic and game-theoretic models of agents interacting on networks.

The course will build on the issues covered in CS 685, but 685 is not a formal pre-requisite for 785. The course will also be structured so as to take advantage of relevant events associated with the Cornell Institute for the Social Sciences' current theme project on "Social Science in the Age of Networks."

Schedule

August 31 (Jon Kleinberg)

Ignacio Palacios-Huerta, Oscar Volij. The Measurement of Intellectual Influence. Econometrica 72:3(2004), 963-977.
Alon Altman and Moshe Tennenholtz. Ranking Systems: The PageRank Axioms. Proceedings of ACM EC 2005.

September 7 (Jon Kleinberg)

M. Jackson and A. Wolinsky. A Strategic Model of Social and Economic Networks. Journal of Economic Theory, Vol. 71, No. 1, 1996, pp 44--74.

September 14 (Lars Backstrom)

M. E. J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)
M. E. J. Newman Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004)

September 21 (Ian Schmutte and Josh Teitelbaum)

A. Calvo-Armengol, M. Jackson. The Effects of Social Networks on Employment and Inequality. American Economic Review, vol. 94, 3 (2004)
A. Calvo-Armengol, M. Jackson. Networks in Labor Markets: Wage and Employment Dynamics and Inequality. Journal of Economic Theory, to appear.
Sections I-IV of the first paper give a condensed picture of the main ideas and model.

September 28 (Georgios Piliouras and Ymir Vigfusson)

D.J. Watts, P.S. Dodds and M.E.J. Newman. Identity and search in social networks. Science, 296, 1302-1305, 2002.
J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.
See also the following two papers for further background and context.
G. Manku, M. Naor, and U. Wieder. Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. In Proc. of ACM Symp. on Theory of Computing (STOC), 2004.
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci. USA, 102(Aug 2005).

October 5 (Bistra Dilkina and Ian Kash)

E Lieberman, C Hauert, MA Nowak (2005). Evolutionary Dynamics on Graphs. Nature 433: 312-316
Ohtsuki H, C Hauert, E Lieberman, MA Nowak (2006). A simple rule for the evolution of cooperation on graphs and social networks. Nature 441: 502-505

October 12 (Thanh Nguyen and Dan Sheldon)

Anders Johansen. Probing human response times. Physica A vol 338, no. 1-2, pp. 286-291 (2004).
A. Vazquez, J. Gama Oliveira, Z. Dezso, K.-I. Goh, I. Kondor, A.-L. Barabasi Modeling bursts and heavy tails in human dynamics. Phys. Rev. E 73, 036127 (2006)
Daniel B. Stouffer, R. Dean Malmgren, Luis A. N. Amaral Log-normal statistics in e-mail communication patterns. arxiv physics/0605027, June 2006.

October 19 (Sasha Gutfraind and Stephen Moseley)

M. Baccara and H. Bar-Isaac. How to Organize Crime. SSRN preprint, April 2006.
A. Calvo-Armengol, Y. Zenou. Social Networks and Crime Decisions: The Role of Social Structure in Facilitating Delinquent Behavior. International Economic Review 45(3), 2004.

October 26 (Tim Carnes and Chris Provan)

Bong-Jun Ko and Dan Rubenstein. A distributed, self-stabilizing protocol for placement of replicated resources in emerging networks. In Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP), Atlanta, GA, November 2003.

November 2 (David Williamson)

P.S. Bearman, J. Moody, and K. Stovel. Chains of affection: the structure of adolescent romantic and sexual networks. American Journal of Sociology, 110:44-91, 2004.

November 9

Institute for the Social Sciences: Workshop on Search and Diffusion in Networks.

November 16 (Yunsong Guo and Asif-ul Haque)

C. Faloutsos, K. McCurley and A. Tomkins. Fast Discovery of Connection Subgraphs. Tenth ACM SIGKDD Conference, Seattle, WA, 2004.

November 23

No lecture: Thanksgiving.

November 30 (Bruno Abrahao and Vladimir Barash)

Petter Holme and M. E. J. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. submitted to Phys. Rev. Lett.

Potential Topics and Papers for Presentations

Many of these also appear in the schedule above.

Decentralized Search

G. Manku, M. Naor, and U. Wieder. Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. In Proc. of ACM Symp. on Theory of Computing (STOC), 2004.
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci. USA, 102(Aug 2005).
Oskar Sandberg and Ian Clarke. The Evolution of Navigable Small-World Networks. arxiv cs.DS/0607025, July 2006.

Agent Interaction on Networks

P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
Cook, K., Emerson, R., Gillmore, M. & Yamagishi, T. 1983. The distribution of power in exchange networks. American Journal of Sociology 89: 275-305.
M. Kearns, S. Suri, and N. Montfort. An Experimental Study of the Coloring Problem on Human Subject Networks. Science 313(5788), August 2006, pp. 824-827.
Petter Holme and M. E. J. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. submitted to Phys. Rev. Lett.
Jure Leskovec, Lada Adamic, Bernardo Huberman. The Dynamics of Viral Marketing. ACM Conference on Electronic Commerce (EC 2006), Ann Arbor, MI, USA, 2006.
M. Kearns, S. Suri. Networks Preserving Evolutionary Stability and the Power of Randomization. ACM Conference on Electronic Commerce, 2006.
Mor Harchol-Balter, Tom Leighton, Daniel Lewin. Resource Discovery in Distributed Networks. ACM Symposium on Principles of Distributed Computing (PODC), 1999, pp. 229-238.
Shay Kutten, David Peleg Deterministic Distributed Resource Discovery. ACM Symposium on Principles of Distributed Computing (PODC), 2000.
Bong-Jun Ko and Dan Rubenstein. A distributed, self-stabilizing protocol for placement of replicated resources in emerging networks. In Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP), Atlanta, GA, November 2003.

The Evolution of Cooperation

E Lieberman, C Hauert, MA Nowak (2005). Evolutionary Dynamics on Graphs. Nature 433: 312-316
Ohtsuki H, C Hauert, E Lieberman, MA Nowak (2006). A simple rule for the evolution of cooperation on graphs and social networks. Nature 441: 502-505
Nowak MA, K Sigmund (2005). Evolution of indirect reciprocity. Nature 437: 1291-1298

Network Growth and Evolution

A. Ntoulas, J. Cho, C. Olston. What's new on the web? The evolution of the web from a search engine perspective. WWW 2004.
Z. Bar-Yossef, A.Z. Broder, R. Kumar, A. Tomkins. Sic Transit Gloria Telae: Towards an understanding of the web's decay. WWW 2004.
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D'Souza, and Robert Kleinberg. Competition-Induced Preferential Attachment. To appear in Combinatorics, Probability, and Computing. Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208-221.
Gueorgi Kossinets and Duncan J. Watts. Empirical Analysis of an Evolving Social Network Science 6 January 2006: Vol. 311. no. 5757, pp. 88 - 90
M. Jackson. A Survey of Models of Network Formation: Stability and Efficiency. In Group Formation in Economics; Networks, Clubs and Coalitions, (G. Demange and M. Wooders, eds.), Cambridge University Press, 2004.
M. Jackson and A. Wolinsky. A Strategic Model of Social and Economic Networks. Journal of Economic Theory, Vol. 71, No. 1, 1996, pp 44--74.
Jacomo Corbo and David C. Parkes. The Price of Selfish Behavior in Bilateral Network Formation. In the Proc. 24rd ACM Symp. on Principles of Distributed Computing (PODC'05), Las Vegas, Nevada, USA, pages 99-107, 2005.
S. Goyal, F. Vega-Redondo. Learning, Network Formation, and Coordination, Games and Economic Behavior 50, 2005

Ranking and Proximity

C. Faloutsos, K. McCurley and A. Tomkins. Fast Discovery of Connection Subgraphs. Tenth ACM SIGKDD Conference, Seattle, WA, 2004.
R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Comparing and Aggregating Rankings with Ties. 23rd ACM Symposium on Principles of Database Systems (PODS 2004).
Alon Altman and Moshe Tennenholtz. Ranking Systems: The PageRank Axioms. Proceedings of ACM EC 2005.

Temporal Dynamics

A..-L. Barabasi. The origin of bursts and heavy tails in human dynamics. Nature 435, 207-211 (2005).
Matthew J. Salganik, Peter Sheridan Dodds, Duncan J. Watts. Experimental Study of Inequality and Unpredictability in an Artificial Cultural Market. Science 10 February 2006: Vol. 311. no. 5762, pp. 854 - 856