Elements of Network Science: CS59000-ENS

Assefaw Gebremedhin
Office: Haas 146
Email: agrebreme at purdue dot edu
http://www.cs.purdue.edu/homes/agebreme
Spring 2013
T-Th 10:30am–11:45am
Recitation Bldg 226
http://www.cs.purdue.edu/homes/agebreme/Networks

Tentative List of Topics

Topics to be covered include the following. Some topics will require multiple lectures. The order in which topics are covered in lectures may differ from the order implied in the list below.

• Graph theory and basic network properties
• Random networks
• The small-world phenomenon
• Decentralized search
• Structure of the WWW
• Power-laws and preferential attachment
• Link analysis and Web search
• Spectral analysis
• Communities
• Cascading behavior in networks
• Epidemic models
• Models of evolving networks

Lectures, Readings, and Announcements

Announcement:
Homework 2 solution is posted.
Homework 2 is out. Due date extended to March 26.
Information on the semester project is out ( (html) (pdf)).
Final Report Guidelines.

Jan 8: LECTURE 1

We went through this course Intro slides. Also handed out this background survey. Please complete and give me this on Thursday 01/11 in class.

Jan 10: LECTURE 2

Topic: Graph Theory: Paths, Distances and Degree Distributions.
Reading: barabasi-chapter2.pdf.

Jan 15: LECTURE 3

Today’s lecture had two topics.

Topic 1: Graph Theory: Connectedness, Components and Clustering Coefficients.
Reading: sections 9–12 of the reading in LECTURE 2.

Topic 2: Network Analysis Software Tools: Intro to igraph.
Resource: We used the igraph website to get introduced to igraph.

Homework 0:

• Browse through the igraph website and gain a quick overview.
• Install the Python version of igraph on your computer (you can use the C version if you wish). To do so, read this page.
• Skim through this Tutorial. For now read just the first two items in the Table of Contents (starting igraph and creating a graph from scratch). You will need to come back to this pagel repeated times as the course proceeds.
• Report to the instructor by email as soon as you complete this or in class at next lecture (Jan 17).

Jan 17: LECTURE 4

Topic: Random Networks.
Reading: barabasi-chapter3.pdf.

Jan 22: LECTURE 5

Topic: We will wrap up discussion on random networks and start discussing a new topic: The small-world phenomenon.

Reading: Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg. Chapter 20. Bibliography. (And here is the entire book)

Further Readings:

• D. Watts and S. Strogatz. Collective dynamics of ”small-world” networks. Nature, 393:440-442,1998.
• S. Milgram. The small-world problem. Psychology Today, 2:60-67, 1967.

Announcement: Homework 1 is out.

Jan 24: LECTURE 6

Topic: Decentralized Search.

Reading:

• Sections 20.3 to 20.6 of Chapter 20 of E&K.
• J. Kleinberg. The small-world phenomenon: an algorithmic perspective. Proc 32nd ACM Symposium on Theory of Computing, pages 163-170, 2000.

Jan 29: LECTURE 7

Topic: Structure of the WWW. Slides

Reading: Chapter 13 of E&K.

Further reading: A. Broder et al. Graph structure in the Web. Computer Networks, 33, 2000.

Jan 31: LECTURE 8

Topic: Power Laws

Readings:

• Chapter 18 of E&K.
• A, Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009. See also the accompanying software at http://tuvalu.santafe.edu/~aaronc/powerlaws/.
• Zipf, Power-laws, and Pareto - a ranking tutorial by Lada Adamic,
  http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html

Announcement: Homework 1 due.

Feb 5: LECTURE 9

Topic: Power Laws, Preferential Attachment and The Long Tail

Readings:

• Sections 18.3 to 18.6 of E&K
• M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226-251, 2004.
• Chris Anderson. The long tail. Wired, October 2004.

Further Readings:

• A.L Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• H. Simon. On a class of skew distribution functions. Biometrika, 42:425-440, 1955.
• D. J. de S. Price. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci. 27: 292-306, 1976.

Feb 7: LECTURE 10

Topic: Navigation in social networks: algorithms and models. Slides

Reading: Section 20.5 of E&K

Further (Optional) Readings:

• D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci., 102, 2005.
• L. A. Adamic, E. Adar. How to search a social network. Social networks, 27 3, 187-203, 2005.
• L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
• D. J. Watts, P. S. Dodds, M. E. J. Newman. Identity and Search in Social Networks. Science, 296, 1302-1305, 2002.
• O’zgur Simsek and David Jensen. Navigating networks by using homophily and degree. Proc. Natl. Acad. Sci. USA, 105(35):12758-12762, Sept 2008.
• A. Clauset and C. Moore. How Do Networks Become Navigable? arXiv:cond-mat/0309415v2, 2003.
• O. Sandberg and I. Clarke. The Evolution of Navigable Small-World Networks. arxiv cs.DS/0607025, 2006.

Feb 12: LECTURE 11

Topic: Centrality

We discussed centrality as a general notion and saw several motivating examples why there exist different centrality measures. We defined structural index (a minimum criterium for a centrality index to satisfy). We then saw four centrality measures: Degree Centrality, Eccentricity Centrality, Closeness (or Transmission) Centrality and Shortest-path Betweenness Centrality.

Reading:
U. Brandes and T. Erlebach (Eds.), Network Analysis: Chapter 3 (Centrality Indices).
Chapters 4 and 5 are also good references.

Feb 14: LECTURE 12

Topic: Plan to discuss Katz Centrality, and then move on to link analysis using Hubs and Authorities.

Reading: Chapter 14 of E&K.

Feb 19: LECTURE 13

David Gleich will give a lecture on PageRank. Lecture Notes.

Feb 26: LECTURE 14

Topic: Spectral analysis. Lecture Notes.

Feb 28: LECTURE 15

Topic: Spectral analysis II. Lecture Notes.

Further Reading:

• U. Brandes and T. Erlebach (Eds.), Network Analysis: Chapter 14 (Spectral Analysis).
• Dan Speilman’s class on Spectral Graph Theory, Fall 2012. (Lectures 1 and 2).

Announcement: Homework 2 is out.

Mar 5: LECTURE 16

We discussed what the semester project involves and how it is setup. More info available here: (html) and (pdf)).

Mar 7: LECTURE 17

Topic: Strong and Weak Ties, and Community Structure

Reading: Chapter 3 of E&K.

Further (Optional) Readings:

• M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360-1380, 1973.
• J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure and tie strengths in mobile communication networks. PNAS, 2007.
• C. Marlow, L. Byron, T. Lento, I. Rosenn. Maintained relationships on Facebook. 2009.
• B.A. Huberman, D.M. Romero, F. Wu. Social networks that matter: Twitter under the microscope. First Monday, 14(1), 2009.
• L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
• P.S. Bearman, J. Moody. Suicide and Friendships Among American Adolescents. Am J Public Health, 94(1): 89-95, 2004.
• R. Burt. Structural Holes versus Network Closure as Social Capital. Chapter in Social Capital: Theory and Research, 2001.
• R. Burt. Structural Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2 2004.
• M. Girvan and M.E.J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 8271-8276, 2002.
• M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
• U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001.

Mar 12

Spring break.

Mar 14

Spring break.

Mar 19: LECTURE 18

Topic: Cascading behavior in networks. Slides

Reading: Chapter 19 of E&K.

Mar 21: LECTURE 19

Topic: Cascade capacity. Slides

Reading: Section 19.7 of Chapter 19 of E&K.

Further (optional) Readings For Lectures 18 and 19:

• Complex Networks Literature
  • D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.
  • A. Montanari and A. Saberi. The spread of innovations in social networks. PNAS 2010.
  • E. Lieberman, C. Hauert, M. A. Nowak. Evolutionary Dynamics on Graphs. Nature 433: 312-316, 2005.
  • N. Immorlica, J. Kleinberg, M. Mahdian, T. Wexler. The Role of Compatibility in the Diffusion of Technologies Through Social Networks. In Proc. ACM EC, 2007.
  • D. Centola, M. Macy, V. Eguiluz. Cascade Dynamics of Multiplex Propagation. Physical Review A 374, 449-456, 2007.
  • D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
  • E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83, 191-200, 2001.
  • P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
  • H. P. Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018.
• Economics/Sociolgy Literature
  • S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
  • D. Centola, M. Macy. Complex Contagions and the Weakness of Long Ties. American Journal of Sociology, 2007.
  • M. Jackson, L. Yariv. Diffusion of Behavior and Equilibrium Properties in Network Games. American Economic Review , Vol 97, No. 2, 2007.
  • S. Bikhchandani, D. Hirshleifer, I. Welch. A theory of fads, fashion, custom and cultural change as information cascades. Journal of Political Economy. Vol. 100, pp. 992-1026, 1992.
  • D. Strang, S. Soule. Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociology, 24:265–290, 1998.
  • A. V. Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, Vol. 107, No. 3, pp. 797-817, 1992.
  • M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.
  • T. Schelling. Micromotives and Macrobehavior. Norton, 1978.

Mar 26: LECTURE 20

Topic: Epidemics on networks - part I. Slides

Reading: Chapter 21 of E&K.

Mar 28: LECTURE 21

Topic: Epidemics on networks - part II. Slides

Reading: Chapter 21 of E&K.

Further (Optional) Readings for Lectures 20 and 21:

• D. Romero, B. Meeder, J. Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter. In Proc. WWW, 2011.
• J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural Diversity in Social Contagion. In Proc. National Academy of Sciences, 2012.
• D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, S. Suri. Sequential Influence Models in Social Networks. In Proc. ICWSM, 2010.
• S. Myers, C. Zhu, J. Leskovec. Information diffusion and external influence in Networks. In Proc. KDD, 2012.
• L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
• M. Miller, C. Sathi, D. Wiesenthal, J. Leskovec, C. Potts. Sentiment Flow Through Hyperlink Networks. In Proc. ICWSM, 2011.
• A. Ganesh , L. Massoulie , D. Towsley. The effect of network topology on the spread of epidemics. In IEEE INFOCOM, 2005.
• S. Myers, J. Leskovec. Clash of the Contagions: Cooperation and Competition in Information Diffusion. In Proc. ICDM 2012.

Apr 2: LECTURE 22

Topic: Diffusion in the blogsphere

Readings:

• H. Kwak, C. Lee, H. Park, S. Moon. What is Twitter, a social network or a news media? In Proc. WWW, 2010. See also slides in slidshare.
• M. Cha, H. Haddadi, F. Benevenuto and K. Gummadi Measuring User Influence in Twitter: The Million Follower Fallacy In ICWSM 2010.
• E. Adar, L. Adamic. Tracking information epidemics in blogspace. In Proc. Web intelligence, 2005.
• D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins. Information Diffusion through Blogspace. In Proc. International WWW Conference, 2004.
• M. Goetz, J. Leskovec, M. Mcglohon, C. Faloutsos. Modeling blog dynamics. In AAAI Conference on Weblogs and Social Media (ICWSM), 2009.

Apr 4: LECTURE 23

Topic: Influence Maximization. Slides

Reading: D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network KDD 2003.

Optional Further Reading:

• Y. Singer. How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks WSDM 2012.
• E. Bakshy, J. Hofman, W. Mason and D. Watts. Everyone’s an Influencer: Quantifying Influence on Twitter WSDM 2012.
• A. Goyal, W. Lu, L. S.V. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model In Proc. ICDM, 2011.
• M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
• M. Richardson, P. Domingos. Mining the Network Value of Customers. In Proc. KDD, 2001.

Apr 9: LECTURE 24

Topic: Networks with positive and negative links. Slides

Reading: Chapter 5 of E&K.

Optional Further Reading:

• J.A. Davis. Structural balance, mechanical solidarity, and interpersonal relations. American Journal of Sociology, 68:444?62, 1963.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. In Proc. CHI, 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. In Proc. WWW, 2010.
• R. Guha, R. Kumar, P. Raghavan, A. Tomkins. Propagation of trust and distrust. In Proc. WWW, 2004.
• J. Kunegis, A. Lommatzsch, C. Bauckhage. The Slashdot Zoo: Mining a social network with negative edges. In Proc. WWW, 2009.
• S. Marvel, S. Strogatz, J. Kleinberg. Energy landscape of social balance. Physical Review Letters, 103, 2009.

Apr 12: LECTURE 25

Topic: Similarity Slides

Reading:

• Sec 7.12 and 13 of the book Networks, An Introduction, by Newman.
• Chapter 4 of E&K.
  

Apr 16: LECTURE 26

Feedback on HW2 (solution here). Then part one of discussion on clustering and communities

Reading: S. Fortunato. Community detection in graphs. Physics Reports 486 (2010).

Apr 18: LECTURE 27

Topic: Clustering and communities II.

References:

• Ulrik von Luxburg. A Tutorial on Spectral Clustering. Stat Comput (2007) 17:395–416.
• R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Trawling the Web for emerging cyber-communities. WWW 1999.
• R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. 20th Int’l Conference on Very Large Databases (VLDB), 1994.
• G. Palla, I. Derenyi, I Farkas and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.

Apr 23: LECTURE 28

Project presentations:

1. Azfar Khandoker and Ryan Miller. Google Set and the Small-World phenomenon. Slides.
2. Sorabh Hamirwasia and Siddhartha Gunda. Decentralized search and network dynamics. Slides.
3. Shubham Agrawal, Ashwin Jiwane and ChoungRyeol Lee. Epidemic models on Facebook networks. Slides.

Apr 25: LECTURE 29

Project presentations:

1. Rodrigo Haragutchi and John Lima. Social network migration: modeling and analysis Slides.
2. Shankaranarayanan P N and Romila Pradhan. Predicting interaction networks and access patterns Slides.
3. Yangyang Hou, Mu Wang and Yongyang Yu. Overlapping communities Slides.

Apr 30

Final project report due. Guidelines.