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."

Scheduling template for coordinating presentation dates.

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)

Potential Topics and Papers for Presentations

More to be added, depending on interests of participants.

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.

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.

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