On this page, you find all the materials (slides, handouts, assignments) organized chronologically. Most importantly, the columns "Important notions/methods" summarize for each lectures the particular definition and method that you need to digest, and will be used in assignments and exams.

Preliminary

Date & Title

Important notions/methods

Readings and Materials

September 8th Welcome to the class

Motivation for learning concepts of social network.
What's in the class? Should you take it?

Lorenz, M. O. (1905). Methods of measuring the concentration of wealth. Publications of the American Statistical Association, 9(70), 209–219.

Simon, H. (1955). On a Class of Skew Distribution Functions. Biometrika, 42(3/4), 425–440.

Yule, G. U. (1925). A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S. Philosophical Transactions of the Royal Society of London. Series BContaining Papers of a Biological Character, 213, 21–87.

Mitzenmacher, M. (2004). A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2), 226–251.

Part A.3 - Which groups are relevant to understand networks?

Date & Title

Important notions/methods

Materials

October 27th Communities and Balance

Divisive and Agglomerative Community Detection,
Modularity, Louvain method, Structural Balance

Dunbar, R. I. M. (1993). Coevolution of Neocortical Size, Group-Size and Language in Humans. Behavioral and Brain Sciences, 16(4), 681–694.

Cartwright, D., & Harary, F. (1956). Structural balance: a generalization of Heider's theory. Psychological Review, 63(5), 277–293. doi:10.1037/h0046049

Part B - Dynamics

Part B.1 - Can we predict the spread of epidemics?

Date & Title

Important notions/methods

Materials

Skipped, materials included for correctness Epidemics

Logistic dynamics, SI, SIS, SIR
Spectral Analysis of epidemic process
Gossip algorithm

Massoulié, L., & Draief, M. (2009). Epidemics and Rumors in Complex Networks (pp. 1–125). Cambridge University Press.

Shah, D. (2009). Gossip Algorithms. Foundations and Trends® in Networking, 3(1).

Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., et al. (1987). Epidemic algorithms for replicated database maintenance. PODC '87: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing.

Part B.2 - Can we leverage properties of influence?

Date & Title

Important notions/methods

Materials

November 10th Adoption, Contagion

Influence, Peer Pressure, Conformity,
Threshold model, Contagion Threshold, Cluster Density

Proof of the naive learning correctness Lecture Notes

Main References:

Degroot, M. H. (1974). Reaching a Consensus. Journal of the American Statistical Association, 69(345), 118–121. doi:10.1080/01621459.1974.10480137

Galton, F. (1907). Vox Populi. Nature, 75(1949), 450–451. doi:10.1038/075450a0

Golub, B., & Jackson, M. O. (2010). Naive learning in social networks and the wisdom of crowds. American Economic Journal: Microeconomics, 2(1), 112–149. doi:10.1257/mic.2.1.112

Part C - Discover

Part C.1 - What is the best way to crawl a graph?

Date & Title

Important notions/methods

Materials

November 24th Random walk for Unbias Crawl and Authentication

Friendship paradox, Crawl, Random Walk
Unbiased estimator, Mixing time, Sybil attack

File Not Found

Main References:

Feld, S. (1991). Why Your Friends Have More Friends than You Do? American Journal of Sociology.

Kurant, M., Gjoka, M., Butts, C., & Markopoulou, A. (2011). Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks. Proceedings of ACM SIGMETRICS.

Levin, D., Peres, Y., & Wilmer, E. (2009). Markov chains and mixing times. Books.Google.com.

Part C.2 - Can we find a posteriori the source of a diffusion?

Part C.3 - Can we recognize users across multiple graphs?

Main References:

Korula, N., & Lattanzi, S. (2014). An efficient reconciliation algorithm for social networks. Proceedings of VLDB, 7(5), 377–388.

Pedarsani, P., & Grossglauser, M. (2011). On the privacy of anonymized networks. Presented at the KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM Request Permissions. doi:10.1145/2020408.2020596

Yartseva, L., & Grossglauser, M. (2013). On the performance of percolation graph matching. Presented at the COSN '13: Proceedings of the first ACM conference on Online social networks, ACM Request Permissions. doi:10.1145/2512938.2512952

Part D - Bird's eye view of 2014 Social Network Research

In parallel to the fundamental results seen in class, we will survey recent papers, primarily taken from the last instalment of the ACM Conference on Online Social Network Conference.

Cohen, E., Delling, D., Pajor, T., & Werneck, R. F. (2014). Computing classic closeness centrality, at scale (pp. 37–50). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660465

Vasconcelos, M., Almeida, J., Gonçalves, M., Souza, D., & Gomes, G. (2014). Popularity dynamics of foursquare micro-reviews (pp. 119–130). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660484

Peddinti, S. T., Ross, K. W., & Cappos, J. (2014). “On the internet, nobody knows you're a dog” (pp. 83–94). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660467

Etter, V., Herzen, J., Grossglauser, M., & Thiran, P. (2014). Mining democracy (pp. 1–12). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660476

An, J., Quercia, D., & Crowcroft, J. (2014). Partisan sharing (pp. 13–24). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660469

Liu, Y., Kliman-Silver, C., Bell, R., Krishnamurthy, B., & Mislove, A. (2014). Measurement and analysis of osn ad auctions. COSN '14: Proceedings of the 2nd ACM Conference on Online Social Networks, 139–150. doi:10.1145/2660460.2660475

Ramachandran, A., Kim, Y., & Chaintreau, A. (2014). “I knew they clicked when i saw them with their friends” (pp. 239–246). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660461

On this page, you find all the materials (slides, handouts, assignments) organized chronologically. Most importantly, the columns "Important notions/methods" summarize for each lectures the particular definition and method that you need to digest, and will be used in assignments and exams.

## Preliminary

Welcome to the classWhat's in the class? Should you take it?

## Part I - Structure

## Part A.1 -

It's a small world, but what kind?A Combinatorial Small WorldRandom Graph, Threshold functions,

Probabilistic Method, Markov Inequality

A Complex Small WorldMonotone properties, Expander

Strong Weak ties, Clustering Coefficient,

Uniformly Augmented Lattice,

Greedy routing, and its failure

An Algorithmic Small WorldCatchupMaterials:Main References:## Part A.2 -

Why is there super nodes and how to find those?Power law and their causesEffect of Heavy tails, Long tail effect,

Power law distribution,

Generative models by reinforcement

The ranking problemIterative methods: Hubs and Authorities Algorithms

CatchupMaterials:Main References:## Part A.3 -

Which groups are relevant to understand networks?Communities and BalanceModularity, Louvain method, Structural Balance

Main References:## Part B - Dynamics

## Part B.1 -

Can we predict the spread of epidemics?EpidemicsSpectral Analysis of epidemic process

Gossip algorithm

Main References:## Part B.2 -

Can we leverage properties of influence?Adoption, ContagionThreshold model, Contagion Threshold, Cluster Density

Main References:## Part B.3 -

When does collective decision reach an optimal choice?Wisdom of the CrowdBalance, Minimal Dispersion, Unif. Prominent Family

Materials:Main References:## Part C - Discover

## Part C.1 -

What is the best way to crawl a graph?Random walk for Unbias Crawl and AuthenticationUnbiased estimator, Mixing time, Sybil attack

File Not FoundMain References:## Part C.2 -

Can we find a posteriori the source of a diffusion?## Part C.3 -

Can we recognize users across multiple graphs?Main References:## Part D - Bird's eye view of 2014 Social Network Research

In parallel to the fundamental results seen in class, we will survey recent papers, primarily taken from the last instalment of the ACM Conference on Online Social Network Conference.

Centrality, Micro-reviews, AnonymityReferences:Democracy and Partisanship, OSN adsReferencesPrivacy to third serviceReferences