Näitä sivuja ei päivitetä enää. Ole hyvä ja katso tietojenkäsittelytieteen laitoksen WWW-sivuja: http://ics.tkk.fi/fi/studies/.

These pages are not any more updated. Please, see web pages of Department of Information and Computer Science (ICS): http://ics.tkk.fi/en/studies/.

Näitä sivuja ei päivitetä enää. Ole hyvä ja katso tietojenkäsittelytieteen laitoksen WWW-sivuja: http://ics.tkk.fi/fi/studies/.

These pages are not any more updated. Please, see web pages of Department of Information and Computer Science (ICS): http://ics.tkk.fi/en/studies/.

T-61.6040 Special Course in Computer and Information Science IV P: Information Networks

Lecturers	PhD (Eng.) Gemma C. Garriga
Assistants	M.Sc. Nikolaj Tatti
Credits (ECTS)	6
Semester	Autumn 2007
Seminar sessions	On Wednesdays at 14-16 in Lecture Hall T4, computer science building, Konemiehentie 2, Otaniemi, Espoo. The first lecture is on September 12th, 2007.
Language	English
Web	http://www.cis.hut.fi/Opinnot/T-61.6040/
E-mail	t616040@cis.hut.fi

Introduction

The goal of the course is to go through a collection of recent research papers on models and algorithms for complex networks. We will study networks such as the Web, the internet, social networks or biological networks, with the objective of learning the common structure and properties. See the reading list for the list of covered topics.

First introductory lecture will be given on 12.09.2007. There will be no lecture on 19.09.07. The rest of the lectures will consist on presentations of the selected research papers by the participants of the seminar.

Prerequisites

The course prerequisites include background in algorithms, graphs, probability and linear algebra.

Requirements for passing the course

To pass the course one needs to participate actively in the lectures (only one absent is allowed), give a presentation (based on a paper chosen from the reading list), do two homework assignments (see section homework), and do a final project (see section project).

Deadlines

• Before 19.09.07 Send the preferred paper and slots for your presentation
• 24.10.07 Submission of the first homework assignment
• 21.11.07 Submission of the second homework assignment
• 8.1.08 Submission of the final project

Homework

Homework will consist on submitting two assignments. Each assignment implies writing a reaction paper. This means:

• Read at least two closely related papers relevant to one of the sections of the course. Chosen papers for an assignment should be: From a topic different from the one you presented and not presented in the class by anyone.

• You should then write approx 3 pages addressing the points:
  • Summary of the technical contents of the papers;
  • Discussion of why the papers are interesting in relation to the chosen section of the course;
  • Discussion of weaknesses and how they could be improved;
  • Discussion of strenghts and promising research questions that arise from the papers.

Project

Project description can be found here.

Presentations

Date	Name	Topic	Slides
12.9	Gemma Garriga	Introduction	[Download]
26.9	Laszlo Kozma	The Anatomy of a Large-Scale Hypertextual Web Search Engine and The PageRank Citation Ranking: Bringing Order to the Web	[Download]
3.10	Janne Toivola	Fast Discovery of Connection Subgraphs and Center-Piece Subgraphs: Problem Definition and Fast Solutions	[Download]
10.10	Markus Ojala	Impact Of Search Engines On Page Popularity	[Download]
17.10	Luis de Alba	What is this Page Known for? Computing Web Page Reputations and Searching the Web	[Download]
24.10	Niko Vuokko	The small-world phenomenon: An algorithmic perspective	[Download]
31.10	Cancelled	Presentation moved to 7.11
7.11	Tiina Lindh-Knuutila	Models of the small world	[Download]
7.11	Mari-Sanna Paukkeri	Information Diffusion through Blogspace	[Download]
14.11	Antti Sorjamaa	Propagation of Trust and Distrust	[Download]
21.11	Samuli Ulmanen	The Dynamics of Viral Marketing
28.11	Ville Lämsä	Graph clustering and On clusterings: good, bad and spectral	[Download]
5.12	Zhi-rong Yang	On clusterings: good, bad and spectral and Finding community structure in networks using the eigenvectors of matrices	[Download]
12.12	Visa Holopainen	The Origin of Power Laws in Internet Topologies Revisited	[Download]

Reading list

The following is a selection of papers for the seminar on Information Networks. Papers are separated by topic groups. Each participant should select for her/his presentation one paper (or a couple of them under the same topic group). Ideally, we will cover different topics with the lectures.

Please, inform about your preferred topic and paper for your presentation by sending an email to t616040@cis.hut.fi. Papers will be handed out in first come first serve fashion. Because this list is far from being complete, you can also propose a paper yourself if not listed below (send an email to discuss about it).

Note that some papers are unavailable outside hut domain.

1. Network models.

• M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003.
• R.Albert and l.A. Barabasi, Statistical Mechanics of Complex Networks, Rev. Mod. PhY~74, 47-97, 2002.
• M. E. J. Newman, Random graphs as models of networks, in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.), Wiley-VCH, Berlin
• W. Aiello, F. Chung, L. Lu. Random evolution of massive graphs. Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer, 2002, pages 97-122.
• S.N. Dorogovtsev, J.F.F. Mendes. Evolution of networks. Adv. Phys. 51, 1079 (2002).
• 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.

2. Power laws and scale free networks.

• M. Faloutsos, P. Faloutsos and C. Faloutsos. On Power-Law Relatonships of the Internet Topology. ACM SIGCOMM 1999.
• M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics.
• M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics, 2004
• B. Bollobas, Mathematical Results in Scale-Free random Graphs.
• L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
• R. Albert. Scale-free networks in cell biology.
• A.-L. Barabasi, Reka Albert, and Hawoong Jeong. Mean-field theory for scale-free random networks. Physica A 272 173-187 (1999).
• B. Bollobas, C. Borgs, J. Chayes, and O. Riordan Directed scale-free graphs Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (2003), 132-139.
• A. Fabrikant, E. Koutsoupias, C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002.
• [Taken] Qian Chen, Hyunseok Chang. Ramesh Govindan, Sugih Jamin, Scott J. Shenker, Walter Willinger. The Origin of Power Laws in Internet Topologies Revisited. Proc. of IEEE Infocom 2002.

3. Small-Worlds: Search and properties.

• V. Nguyen and C. Martel. Analyzing and characterizing small-world graphs. 2005 ACM-SIAM symposium on Discrete Algorithms.
• D.J. Watts. Networks, Dynamics and Small-World Phenomenon, American Journal of Sociology, Vol. 105, Number 2, 493-527, 1999
• [Taken] J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000
• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.
• D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks, Science 296, 1302-1305 (2002).
• Adamic L., Lukose R., Puniyani A., and Huberman B., Search in power law networks, Physical review Vol 64.
• L. Adamic, E. Adar. How To Search a Social Network. Social Networks Journal. Vol 27, Is 3, 2005, Pages 187-203
• J. Leskovec, J. Kleinberg, C. Faloutsos: Graphs over time: densification laws, shrinking diameters and possible explanations. KDD 2005: 177-187
• [Taken] M. E. J. Newman, Models of the small world, J. Stat. Phys. 101, 819-841 (2000).

4. The Web Graph.

• A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the web. 9th International World Wide Web Conference, May 2000.
• J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. The Web as a graph: Measurements, models and methods. Invited survey at the International Conference on Combinatorics and Computing, 1999.
• K. Bharat and A. Broder. A technique for measuring the relative size and overlap of public Web search engines. Proc. 7th International World Wide Web Conference, 1998.
• S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. 27th International Conference on Very large Data Bases, 2001.

5. Web search, Link analysis, Spectral analysis.

• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
• [Taken] S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Mining the link structure of the World Wide Web. IEEE Computer, August 1999.
• [Taken] A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan. Searching the Web. ACM Transactions on Internet Technology 1(1): 2-43 (2001)
• A. Borodin, J. S. Rosenthal, G. O. Roberts, P. Tsaparas, Finding Authorities and Hubs From Link Structures on the World Wide Web. 10th International World Wide Web Conference, May 2001.
• A. Borodin, G. Roberts, J. Rosenthal, P. Tsaparas, Link Analysis Ranking: Algorithms, Theory and Experiments, ACM Transactions on Internet Technologies (TOIT), 5(1), 2005
• P. Tsaparas, Using Non-Linear Dynamical Systems for Web Searching and Ranking, Principles of Database Systems (PODS), Paris, 2004
• Dimitris Achlioptas, Amos Fiat, Anna Karlin, Frank McSherry, Web Search via Hub Synthesis. 42nd IEEE Symposium on Foundations of Computer Science, 2001, p.611-618.
• [Taken] Davood Rafiei, Alberto Mendelzon. What is this Page Known for? Computing Web Page Reputations. Proc. WWW9 Conference, Amsterdam, May 2000
• Pedro Domingos, Matt Richardson. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. Advances in Neural Information Processing Systems 14, 2002.
• Taher H. Haveliwala. Topic-Sensitive PageRank. 11th International World Wide Web Conference, 2002.
• Alon Altman and Moshe Tennenholtz. Ranking Systems: The PageRank Axioms. Proceedings of ACM EC 2005.
• A. Y. Ng, A. X. Zheng, and M. I. Jordan. Link analysis, eigenvectors, and stability. International Joint Conference on Artificial Intelligence (IJCAI), 2001.
• S. Chien, C. Dwork, R. Kumar, D. Simon, and D. Sivakumar, Link Evolution: Analysis and Algorithms
• A. Y. Ng, A. X. Zheng, and M. I. Jordan. Stable algorithms for link analysis. 24th International Conference on Research and Development in Information Retrieval (SIGIR 2001).
• L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.
• R. Lempel and S. Moran, Rank Stability and Rank Similarity of Link-Based Web Ranking Algorithms in Authority Connected Graphs, Information Retrieval 8 (special issue on advances in mathematics/formal methods in information retrieval), pp. 245-264, 2005.
• Ziv Bar-Yossef, Alexander Berg, Steve Chien, Jittat Fakcharoenphol, and Dror Weitz. Approximating Aggregate Queries about Web Pages via Random Walks. 26th International Conference on Very Large Databases (VLDB), 2000, pages 535-544.
• Soumen Chakrabarti, Mukul Joshi, Kunal Punera, and David M. Pennock. The structure of broad topics on the Web. 11th World Wide Web conference, May 2002.
• Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar. Rank Aggregation Methods for the Web. 10th International World Wide Web Conference, May 2001.
• Weiyi Meng, Clement Yu, King-Lup Liu. Building Efficient and Effective Metasearch Engines. ACM Computing Surveys 34(2002).
• T. Joachims. Optimizing Search Engines Using Clickthrough Data. Eighth International Conference on Knowledge Discovery and Data Mining, KDD-2002.
• Ron Fagin, Ravi Kumar and D. Sivakumar. Comparing top k lists, Extended abstract in 2003 ACM-SIAM Symposium on Discrete Algorithms (SODA '03), pp. 28-36.
• Ron Fagin, Ravi Kumar and D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proc. 2003 ACM SIGMOD Conference (SIGMOD '03), pp. 301-312.
• [Taken] J. Cho, S. Roy, Impact Of Search Engines On Page Popularity, WWW 2004
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. 12th International Conference on Information and Knowledge Management (CIKM), 2003.
• Zoltán Gyöngyi, Hector Garcia-Molina. Link Spam Alliances. 31st International Conference on Very Large Data Bases (VLDB), Trondheim, Norway, 2005.

6. Propagation effects in networks: gossips, epidemics and trust.

• Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance. Cost-effective Outbreak Detection in Networks. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM KDD), 2007.
• P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
• Pedro Domingos, Matt Richardson. Mining Knowledge-Sharing Sites for Viral Marketing. Eighth International Conference on Knowledge Discovery and Data Mining, KDD-2002.
• Pedro Domingos, Matt Richardson. Mining the Network Value of Customers, Proceedings of the Seventh International Conference on Knowledge Discovery and Data Mining (pp. 57-66), 2001.
• D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.
• [Taken] D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins. Information Diffusion through Blogspace. Proc. International WWW Conference, 2004.
• D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• R. Karp, C. Schindelhauer, S. Shenker, B. Vocking. Randomized Rumor Spreading. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• [Taken] Jure Leskovec, Lada Adamic, Bernardo Huberman. The Dynamics of Viral Marketing. ACM Transactions on the Web (ACM TWEB), 1(1), 2007.
• Jure Leskovec, Mary McGlohon, Christos Faloutsos, Natalie Glance, Matthew Hurst. Cascading Behavior in Large Blog Graphs SIAM International Conference on Data Mining (SDM) 2007.
• Y.ang Wang, Deepayan Chakrabarti, Chenxi Wang, Christos Faloutsos, Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint, SDRS, 2003
• M. Richardson, R. Agrawal, and P. Domingos, Trust Management for the Semantic Web, Proc. of Int. Semantic Web Conf. 2003, PP.351-368.
• [Taken] R. Guha and R. Kumar, Propagation of Trust and Distrust, WWW2004, New York, 2004.
• A. Calvo-Armengol, M. Jackson. Networks in Labor Markets: Wage and Employment Dynamics and Inequality. Journal of Economic Theory, to appear.
• 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), 200
• Zoltán Gyöngyi, Hector Garcia-Molina, Jan Pedersen. Combating Web Spam with TrustRank. 30th International Conference on Very Large Data Bases (VLDB), Toronto, Ontario, Canada, 2004.

7. Clustering and community structure.

• Chayant Tantipathananandh, Tanya Berger-Wolf, David Kempe A Framework for Community Identification in Dynamic Social Networks. KDD 2007, San Jose, CA.
• [Taken] M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74, 036104 (2006).
• R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Trawling the web for emerging cyber-communities. 8th International World Wide Web Conference, May 1999.
• A. Clauset. Finding local community structures in networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):026132. 2005.
• Hopcroft, O. Khan, B. Kulis, and B. Selman. Natural communities in large linked networks. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 541--546,
• [Taken] Ravi Kannan, Santos Vempala, Adrian Vetta, On clusterings: good, bad and spectral. Journal of the ACM (JACM) 51(3), 497--515, 2004.
• E. A. Leicht, Petter Holme, and M. E. J. Newman, Vertex similarity in networks, Phys. Rev. E 73, 026120 (2006).
• 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)
• [Taken] C. Faloutsos, K. McCurley and A. Tomkins. Fast Discovery of Connection Subgraphs. In Tenth ACM SIGKDD Conference, Seattle, WA, 2004.
• [Taken] Satu Elisa Schaeffer. Graph Clustering. Computer Science Review 1(1):27-64,2007.

8. Games and networks.

• Christos H. Papadimitriou, Algorithms, Games, and the Internet. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• L. Blume, D. Easley, J. Kleinberg and E. Tardos. Trading Networks with Price-Setting Agents. EC'07.
• T. Roughgarden and E. Tardos. How Bad is Selfish Routing? Journal of the ACM, 2002, Volume 49 , Issue 2.
• E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS 2004.

9. Biological networks.

• A.-L. Barabási and Z. N. Oltvai. Network Biology: Understanding the Cell's Functional Organization. Nature Reviews Genetics 5, 101-113 (2004)
• Kevin Bleakley, Gérard Biau and Jean-Philippe Vert. Supervised reconstruction of biological networks with local models. ISMB/ECCB 2007.

10. Still you did not find anything interesting ... ?

Then, you can propose a paper not listed above within the area of information networks. Similar seminars with more online papers are for example: The Structure of Information Networks, at Cornell University and the Seminar on Social Networks, at University of Toronto.

Send an email to t616040@cis.hut.fi with your proposal and we will discuss about it.