CS224W:
Social and Information Network Analysis
Autumn 2015
Handouts
Homework
- Homework 0 (Due at 9:00am Oct. 1, 2015). Submission Template for HW0 [pdf | tex | docx]. Solutions [PDF][Code].
- Homework 1 (Due at 9:00am Oct. 8, 2015). Submission Template for HW1 [pdf | tex | docx]. Solutions [PDF][Code].
- Homework 2 (Due at 9:00am Oct. 22, 2015). Submission Template for HW2 [pdf | tex | docx]. Solutions [PDF][Code].
- Homework 3 (Due at 9:00am Nov. 05, 2015). Submission Template for HW3 [pdf | tex | docx]. Solutions [PDF][Code].
- Homework 4 (Due at 9:00am Nov. 19, 2015). Submission Template for HW4 [pdf | tex | docx].
Recitations
Lecture notes and further reading
Pointers to the slides will be posted here just before the start of the class.
NOTE: Syllabus is still evolving and will be finalized by 09/22
09/22: What are networks and what use is it to study them? [Slides]
Reading:- Easley & Kleinberg, Networks, Crowds and Markets, Ch1. Overview.
- Albert-László Barabási, Network Science, Ch 1. Introduction
- Albert-László Barabási, Network Science, Ch 2, sections 2-6,9
- Linked by Albert-László Barabási
- Six Degrees by Duncan Watts.
- other notables: Nexus by Mark Buchanan and Connected by Nicholas Christakis and James Fowler.
09/24: Centrality [Slides]
Reading:- Wayne E. Baker and Robert R. Faulkner, The Social Organization of Conspiracy: Illegal Networks in the Heavy Electrical Equipment Industry, American Sociological Review, Vol. 58, No. 6 (Dec, 1993)
- Burt, Ronald S. Structural holes and good ideas. American journal of sociology 110.2 (2004): 349-399.
- Newman, Mark. Who is the best connected scientist? A study of scientific coauthorship networks. Complex networks (2004): 337-370.
- Han, Jing-Dong J., et al. Evidence for dynamically organized modularity in the yeast protein–protein interaction network. Nature 430.6995 (2004): 88-93.
09/29: Random graphs [Slides]
Reading:- Easley & Kleinberg, Chapter 2: Graphs
- P. Erdos, A. Renyi. On Random Graphs I. Publ. Math. Debrecen, 1959.
- P. Erdos, A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
- B. Bollobas. Random Graphs. Cambridge University Press.
- M.E.J. Newman, S. H. Strogatz and D.J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118, 2001.
- R. Milo, N. Kashtan, S. Itzkovitz, M.E.J. Newman, U. Alon. On the uniform generation of random graphs with prescribed degree sequences. Arxiv, 2004.
- D. Ellis. The expansion of random regular graphs. Lecture notes from Algebraic methods in combinatorics, Cambridge University, 2011.
- S. Arora, S. Rao and U. Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. In proc. STOC '04, 2004.
10/01: Powers laws and Preferential attachment [Slides]
Reading:- Easley & Kleinberg Chapter 18: Power Laws and Rich-Get-Richer Phenomena
- A.L Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
- M.E.J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46(5), 323-351, 2005.
- M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
- A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009.
- M. Faloutsos, P. Faloutsos, C. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proc. SIGCOMM, 1999.
- B.A. Huberman, L. A. Adamic. Growth dynamics of the World-Wide Web. Nature, 399, 1999.
- H.A. 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.
- A.L. Barabasi, R. Albert, H. Jeong. Mean-field theory for scale-free random networks. Physica A 272 173-187, 1999.
- R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models for the Web graph. In Proc. FOCS 2000.
- W. Aiello, F. Chung, L. Lu. Random evolution of massive graphs. Handbook of Massive Data Sets, Kluwer, pages 97-122, 2002.
- B. Bollobas, C. Borgs, J. Chayes, O. Riordan. Directed scale-free graphs. In Proc. SODA 2003.
- R. Kleinberg, J. Kleinberg. Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. In Proc. SODA, 2005.
- A. Fabrikant, E. Koutsoupias, C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proc. ICALP, 2002.
- N. Berger, C. Borgs, J. Chayes, R. D'Souza, R. Kleinberg. Competition-Induced Preferential Attachment. In Proc. ICALP 2004.
- M. Molloy and B. Reed. A Critical Point for Random Graphs with a Given Degree Sequence. Random Structures and Algorithms 6, 161-180, 1995.
- J. Carlson and J. Doyle. Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. Physical Review E 60:2, 1999.
- M.E.J. Newman. The first-mover advantage in scientific publication. European Physics Letters 86, 68001, 2009.
- S. Redner. Citation statistics from 110 years of Physical Review. Physics Today 58, 49-54, 2005.
- S. Goel, A. Broder, E. Gabrilovich, B. Pang. Anatomy of the Long Tail: Ordinary People with Extraordinary Tastes. In Proc. WSDM, 2010.
- D. Pennock, G. Flake, S. Lawrence, E. Glover, C. Lee Giles. Winners don't take all: Characterizing the competition for links on the web. PNAS 99(8), 2002.
10/06: Small-world networks and decentralized search[Slides]
Reading:- J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. ACM Symposium on Theory of Computing, 2000.
- M. E. J. Newman. Models of the Small World: A Review., J. Stat. Physics 2000.
- J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS), 2001.
- D. J. Watts, P. S. Dodds, M. E. J. Newman. Identity and Search in Social Networks. Science, 296, 1302-1305, 2002.
- A. Clauset and C. Moore. How Do Networks Become Navigable? arXiv:cond-mat/0309415v2, 2003.
- L. A. Adamic, E. Adar. How to search a social network. Social networks, 27 3, 187-203, 2005.
- Travers, Jeffrey, and Stanley Milgram.An experimental study of the small world problem. Sociometry (1969): 425-443.
- Killworth, Peter D., et al. The accuracy of small world chains in social networks. Social networks 28.1 (2006): 85-96.
- D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. In Proc. Natl. Acad. Sci., 102, 2005.
- R. West, J. Leskovec. Human Wayfinding in Information Networks. In Proc. WWW, 2012.
- R. West, J. Leskovec. Automatic versus Human Navigation in Information Networks. In Proc. ICWSM, 2012.
- G. Manku, M. Naor, U. Wieder. Know thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. Proc. STOC 2004.
- E-K Lua, J. Crowcroft, M. Pias, R. Sharma and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys and Tutorials, 2005.
- O. Sandberg and I. Clarke. The Evolution of Navigable Small-World Networks. arxiv cs.DS/0607025, 2006.
- I. Clarke, O. Sandberg, B. Wiley, T. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. International Workshop on Design Issues in Anonymity and Unobservability, 2000.
- I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Proc. SIGCOMM, 2001.
10/08: Social network analysis applications (Part I) [Slides]
Reading:- R. Milo et al. Superfamilies of evolved and designed networks, Science, 2004.
- Zhang, Jun, Mark S. Ackerman, and Lada Adamic. Expertise networks in online communities: structure and algorithms. WWW'07. ACM, 2007.
- Sinan Aral and Marshall Van Alstyne,Network Structure and Information Advantage, working paper (full, longer paper published as The Diversity-Bandwidth Trade-Off,American Journal of Sociology, 2011.
- Motifs: simple building blocks of complex networks
- R. Burt. Structural Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2 2004.
- 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
- Adamic, L. A., Zhang, J., Bakshy, E., & Ackerman, M. S. Knowledge sharing and yahoo answers: everyone knows something. WWW'08.
- Fowler, James H. Connecting the Congress: A study of cosponsorship networks. Political Analysis 14.4 (2006): 456-487.
- L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
- C.Y. Teng, Y.R. Lin, L.A. Adamic, Recipe recommendation using ingredient networks,WebSci'12.
10/13: Link Analysis and ranking [Slides]
Reading:- Chapter 14: Link Analysis and Web Search.
- L Page, S Brin, R Motwani, T Winograd,The PageRank citation ranking: bringing order to the Web, Stanford technical report.
- H Kwak, C Lee, H Park, S Moon,What is Twitter, a social network or a news media?,WWW'10 (Sameep's recommendation).
- S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998.
- J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
- P. Berkhin. A Survey of PageRank Computing. Internet Mathematics, 2005.
- 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.
- 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.
- D. Achlioptas, A. Fiat, A. Karlin, F. McSherry. Web Search via Hub Synthesis. 42nd IEEE Symposium on Foundations of Computer Science, p.611-618, 2001.
- D. Rafiei, A. Mendelzon. What is this Page Known for? Computing Web Page Reputations. Proc. WWW Conference, 2000.
- P. Domingos, M. Richardson. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. In Proc. NIPS, 2002.
- T. H. Haveliwala. Topic-Sensitive PageRank. 11th International World Wide Web Conference, 2002.
- A. Altman, M. Tennenholtz. Ranking Systems: The PageRank Axioms. In Proc. of ACM EC, 2005.
- Z. Gyongyi, H. Garcia-Molina, J. Pedersen. Combating Web Spam with TrustRank. In Proc. of VLDB, 2004.
- Z. Gyongyi, P. Berkhin, H. Garcia-Molina, J. Pedersen. Link Spam Detection Based on Mass Estimation. In Proc. of VLDB, 2006.
- A. Borodin, G. O. Roberts, J. S. Rosenthal, P Tsaparas. Link Analysis Ranking: Algorithms, Theory, and Experiments. ACM TOIT, 2005.
- A. Ntoulas, J. Cho, C. Olston. What’s New on the Web? The Evolution of the Web from a Search Engine Perspective. In Proc. WWW, 2004.
- M. A. Najork. Comparing the effectiveness of HITS and SALSA. In Proc. CIKM, 2007.
- B. Bahmani, A. Chowdhury, A. Goel. Fast Incremental and Personalized PageRank. In Proc. of VLDB, 2010.
10/15: Diffusion and cascades [Slides]
Reading:- Easley & Kleinberg: Chapter 21: Epidemics
- Easley & Kleinberg: Chapter 19: Cascading Behavior in Networks
- S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
- 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.
- E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83, 191-200, 2001.
- D. Centola, M. Macy. Complex Contagions and the Weakness of Long Ties. American Journal of Sociology, 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.
- T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
- D. Strang, S. Soule. Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociology, 24:265--290, 1998.
- D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
- H. P. Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018.
- P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
- E. Lieberman, C. Hauert, M. A. Nowak. Evolutionary Dynamics on Graphs. Nature 433: 312-316, 2005.
- D. Centola, M. Macy, V. Eguiluz. Cascade Dynamics of Multiplex Propagation. Physica A 374, 449-456, 2007.
- D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.
- M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.
- A. V. Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, Vol. 107, No. 3, pp. 797-817, 1992.
- Bakshy, Rosenn, Marlow, and Adamic,The role of social networks in information diffusion,Proc. WWW, 2012
10/20: Visualization [Slides]
Tools we will discuss: Reading:- All the publications on mapequation.org
10/22: Opinion formation [Slides]
Reading:- Easley & Kleinberg, Ch 19
- Damon Centola,,'The spread of behavior in an online social network experiment', Science, 2010.
- B. State and L. Adamic,The Diffusion of Support in an Online Social Movement: Evidence from the Adoption of Equal-Sign Profile Pictures,CSCW'15.
- A Banerjee, AG Chandrasekhar, E Duflo, MO Jackson,The diffusion of microfinance, Science 341.6144 (2013): 1236498.
- A. Banerjee, A.G. Chandrasekhar, E. Duflo, and M.O. Jackson, Gossip: Identifying Central Individuals in a Social Network, 2014.
- M. O. Jackson, Social and Economics Networks Ch 8: Learning and Networks
10/27: Influence maximization (whiteboard lecture, check the handout)
Reading:10/29: Community structure [Slides]
Reading:- Chapter 3: Strong and Weak Ties.
- 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. Modularity and community structure in networks., Proc. Natl. Acad. Sci., 2002.
- 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. Chapeter in Social Capital: Theory and Research, 2001.
- G. Flake, S. Lawrence, C.L. Giles, F. Coetzee. Self-Organization and Identification of Web Communities. IEEE Computer, 35:3, 2002.
- G. Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Technical Report 2002-06, NEC, Princeton, NJ, 2002.
- S. Fortunato Community detection in graphs, Arxiv 2009.
- A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004
- 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.
- J. Reichardt, S. Bornholdt. Statistical Mechanics of Community Detection., Phys. Rev. E 74 016110, 2006.
- S. Fortunato, S. Barthelemy. Resolution limit in community detection. Proc. Natl. Acad. Sci., 2007.
- U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, D. Wagner. On Modularity Clustering. IEEE TKDE, 2007.
- G. Palla, I. Derenyi, I. Farkas, T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.
- E. Tomita, A. Tanaka, H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, Volume 363, Issue 1, 2006.
- G. Palla, A.L. Barabasi, T. Vicsek. Quantifying social group evolution. Nature 446, 664-667, 2007.
- J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks. In Proc. WWW, 2008.
- J. Leskovec, K. Lang, M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In Proc. WWW, 2010.
- J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, 2009.
- G. Karypis, V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. J. Parallel Distrib. Comput, 48(1): 96-129, 1998.
- I. Dhillon, Y. Guan, and B, Kulis. A Fast Kernel-based Multilevel Algorithm for Graph Clustering. In Proc. KDD, 2005.
- R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.
- T. Leighton, S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 1999.
11/03: Agent based modeling of networks [Slides]
Tools we will discuss: Optional reading- Gilbert, G. Nigel. Agent-based models. No. 153. Sage, 2008.
- Miller, John H., and Scott E. Page. Complex adaptive systems: an introduction to computational models of social life: an introduction to computational models of social life. Princeton university press, 2009.
- Axelrod, Robert, and William Donald Hamilton. "The evolution of cooperation." Science 211.4489 (1981): 1390-1396.
- Ross A. Hammond and Robert Axelrod, The Evolution of Ethnocentrism,Journal of Conflict Resolution 50.6 (2006): 926-936..
- Zhihui Wanga, Joseph D. Butnerb, Romica Kerkettaa, Vittorio Cristinia, Thomas S. Deisboeckd. Simulating cancer growth with multiscale agent-based modeling.
- Magda Fontana, Pietro Terna. From Agent-based models to network analysis (and return): the policy-making perspective.
- Elmar Kiesling, Markus Günther, Christian Stummer, Lea M. Wakolbinger. Agent-based simulation of innovation diffusion: a review
- William Randa, Roland T. Rust. Agent-based modeling in marketing: Guidelines for rigor
11/05: Formation and evolution [Slides]
Reading:- J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins. Microscopic Evolution of Social Networks. In Proc. KDD 2008.
- Guimera, Roger, et al. Team assembly mechanisms determine collaboration network structure and team performance. Science 308.5722 (2005): 697-702.
- Holme, Petter, and Gourab Ghoshal. Dynamics of networking agents competing for high centrality and low degree. Physical review letters 96.9 (2006): 098701.
- M.O. Jackson, Social and Economic Networks, Ch. 6: Strategic network formation.
- Ravi Kumar, Jasmine Novak, and Andrew Tomkins. Structure and Evolution of Online Social Networks. KDD 2006.
- Elena Zheleva, Hossam Sharara, and Lise Getoor. Co-evolution of Social and Affiliation Networks. KDD 2009.
- B Bringmann, M Berlingerio, and F Bonchi. Learning and Predicting the Evolution of Social Networks. IEEE INTELLIGENT SYSTEMS 2010.
- Gergely Palla, Albert-László Barabási, and Tamás Vicsek. Quantifying social group evolution. Nature 2007.
- MO Jackson. A survey of network formation models: stability and efficiency. In: Group Formation in Economics: Networks, Clubs, … 2005.
11/10: Topic mish-mash I: Games and learning on networks, signed edges [Slides]
Reading:- Michael Kearns, Siddarth Suri,Nick Montfort, An Experimental Study of the Coloring Problem on Human Subject Networks, Science 313, 824 (2006).
- M. Jackson, L. Yariv. Diffusion of Behavior and Equilibrium Properties in Network Games. American Economic Review , Vol 97, No. 2, 2007.
- M.O. Jackson, Social and Economic Networks, Ch. 9: Decisions, Behavior, and Games on Networks.
- Zhen Wang, Lin Wang, Attila Szolnoki, Matjaž Perc. Evolutionary games on multilayer networks: a colloquium.
- Matthew O. Jackson, Yves Zenou. Games on Networks.
- Gary Charness, Francesco Feri, Miguel Melendez-Jimenez, Matthias Sutter. Experimental Games on Networks: Underpinnings of Behavior and Equilibrium Selection.
- D. Cartwright, F. Harary. Structural balance: A generalization of Heider's theory. Psychological review, 1956.
- F. Heider. Attitudes and cognitive organization. Journal of Psychology. 21, 107-112, 1946.
- 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.
- T. Antal, P. Krapivsky, S. Redner. Dynamics of Social balance on Networks. Phys. Rev. E, 2005.
- S. Marvel, S. Strogatz, J. Kleinberg. Energy landscape of social balance. Physical Review Letters, 103, 2009.
- S. Marvel, J. Kleinberg, R. Kleinberg, S. Strogatz. Continuous-Time Model of Structural Balance. Proc. National Academy of Sciences, 2011.
- J.A. Davis. Structural balance, mechanical solidarity, and interpersonal relations. American Journal of Sociology, 68:444-62, 1963.
- P. Doreian, A. Mrvar. A partitioning approach to structural balance. Social. Networks 18, 1996.
- M. J. Brzozowski, T. Hogg, G. Szabo. Friends and foes: ideological social networking. In Proc. CHI, 2008.
- P. Doreian. Evolution of human signed networks. In Metodološki zvezki, 2004.
- C. J. Hsieh, K Chiang, and I. S. Dhillon. Low-Rank Modeling of Signed Networks. In Proc. KDD, 2012.
- K. Chiang, I. S. Dhillon, N. Natarajan, and A. Tewari. Exploiting Longer Walks for Link Prediction in Signed Network. In Proc. CIKM, 2011.
- G. Facchetti, G. Iacono, C Altafini. Computing global structural balance in large-scale signed social networks. In Proc. National Academy of Sciences, 2011.
- M. Szell, R. Lambiotte, S. Thurner. Multirelational Organization of Large-scale Social Networks in an Online World. Proc. National Academy of Sciences, 2010.
- J. Kunegis, A. Lommatzsch, C. Bauckhage. The Slashdot Zoo: Mining a social network with negative edges. In Proc. WWW, 2009.
11/12: Topic mish-mash 2: assortativity, resilience, link-prediction [Slides]
Assortativity and resilience
Reading:- R Albert, H Jeong, AL Barabási,Error and attack tolerance of complex networks,Nature, 2000.
- MEJ Newman,Mixing patterns in networks, Phys. Rev. E, 2003.
- L. Backstrom, J. Leskovec. Supervised Random Walks: Predicting and Recommending Links in Social Networks. In Proc. WSDM, 2011.
11/17: Guest lecture Jure Leskovec: Outbreak detection [Slides]
Reading:- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance. Cost-effective Outbreak Detection in Networks. In Proc. KDD, 2007.
- E. Mossel and S. Roch. On the Submodularity of Influence in Social Networks. In Proc. STOC, 2007.
- N. Agarwal, H. Liu, L. Tang, P. Yu. Identifying the Influential Bloggers in a Community In Proc. WSDM, 2008.
- A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, C. Faloutsos. Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks. Journal of Water Resources Planning and Management, 2008.
- A. Krause, C. Guestrin, A Note on the Budgeted Maximization on Submodular Functions. Technical report, Carnegie Mellon University, no. CMU-CALD-05-103, 2005.
- A. Ostfeld et al. The Battle of the Water Sensor Networks (BWSN): A Design Challenge for Engineers and Algorithms. Journal of Water Resources Planning and Management, 2009.
- M. Cha, H. Haddadi, F. Benevenuto, K.P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. ICWSM, 2010.
- A. Goyal, W. Lu, L. V.S. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In Proc. WWW, 2011.
- R. Pastor-Satorras, A. Vespignani. Immunization of complex networks. Physical Review E, 2002.
- T. Lappas, E. Terzi, D. Gunopoulos, H. Mannila. Finding Effectors in Social Networks. In Proc. KDD, 2010.
12/01: Social influence: a guest Lecture by Facebook's Sean Taylor
Reading:- L. Muchnik, S. Aral, S. J. Taylor. Social Influence Bias: A Randomized Experiment. Science, Vol. 341 no. 6146 pp. 647-651, 2013.
- S. Aral and D. Walker, Identifying influential and susceptible members of social networks, Science, Vol. 337 no.6092 (2012): 337-341.
- M. J. Salganik, P.S. Dodds, and D. J. Watts. Experimental study of inequality and unpredictability in an artificial cultural market. Science Vol. 311 No. 5762 (2006): 854-856.
- E. Bakshy, D. Eckles, R. Yan, I. Rosenn. Social influence in Social Advertising: Evidence from Field Experiments, EC'12.
12/03: Network analysis at Facebook scale: a guest Lecture by Facebook's Dionysios Logothetis
Reading:- A. Ching, S. Edunov, M. Kabiljo, D. Logothetis, and S. Muthukrishnan. One Trillion Edges: Graph Processing at Facebook-Scale, VLDB'15. (or read the short post).
Other fun reading
- (Rohit recommends): Leskovec, Jure, and Julian J. Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems. 2012.
- (Rohit recommends): Glen Jeh and Jennifer Widom. SimRank: A measure of structural-context similarity
- (Nihit recommends): Kristina Lerman, Xiaoran Yan, and Xin-Zeng Wu, The Majority Illusion in Social Networks.
- (Caroline recommends) Cheng, J., Adamic, L., Dow, P. A., Kleinberg, J. M., & Leskovec, J., Can cascades be predicted?,WWW'14.
- (Tim recommends) E. Bakshy, S. Messing, L. Adamic, Exposure to ideologically diverse news and opinion on Facebook, Science 348(6239), 1130-1132, 2015.
- (Time recommends)How Community Feedback Shapes User Behavior. Justin Cheng, Cristian Danescu-Niculescu-Mizil, Jure Leskovec Proceedings of ICWSM, 2014.
- (Paris recommends) Adcock, Aaron B., Blair D. Sullivan, and Michael W. Mahoney. Tree decompositions and social graphs." arXiv preprint arXiv:1411.1546 (2014).
- (Paris recommends) Abu-Ata, Muad, and Feodor F. Dragan. Metric tree-like structures in real-life networks: an empirical study. arXiv preprint arXiv:1402.3364 (2014).