This website contains all the information in the syllabus. You can
simply print this website.
Date | Readings | Moderator |
1/10 |
Introduction and Misc.
Further reading:
|
YY |
Small world |
1/12 |
Required reading:
- S. Milgram, The
Small-World Problem, Pscyhology today, 1967.
- J. Travers and S. Milgram, An
Experimental Study of the Small World Problem,
Sociometry, 1969
- Paper 1: P.S. Dodds et al., An
Experimental Study of Search in Global Social Networks,
Science, 2003.
- Paper 2: L. Backstrom et al., Four Degrees of
Separation, arXiv, 2011.
Further reading:
- Easley & Kleinberg, Ch. 20
- J. Leskovec and E. Horvitz, Planetary-scale views on a large instant-messaging network, WWW'08
- C.R. Palmer et al., ANF: A fast and scalable tool for data mining in massive graphs, KDD'02.
- P. Flajolet and G.N. Martin, Probabilistic counting algorithms for data base applications, J. Comp. Sys. Sci. , 1985.
- R. Bhide, Flajolet-Martin
algorithm.
- P. Boldi and S. Vigna, The
WebGraph framework I: compression techniques,
WWW'04.
- P. Boldi et al., Layered label
propagation: a multiresolution coordinate-free ordering for
compressing social networks, arXiv, 2011
|
Shantanu
Dimitar |
Small world / clustering / weak ties |
1/17 |
Required reading:
- M.S. Granovetter, The
Strength of Weak Ties, American Journal of
Sociology, 1973.
- Easley & Kleinberg, Ch.3
- Paper 1: D.J. Watts and S.H. Strogatz, Collective
Dynamics of 'Small-World' Networks, Nature,
1998.
- Paper 2: J.P. Onnela et al., Structure
and tie strengths in mobile communication networks,
PNAS, 2007.
Further reading:
|
Ian |
Communities / clustering / weak ties |
1/19 |
Required reading:
Further reading:
- U. Brandes, A faster algorithm for betweenness centrality, J. Math. Soc., 2001
- B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Systems Technical Journal, 1970.
- M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks, PRE, 2004.
- F. Radicchi et al., Defining and identifying communities in networks, PNAS, 2004.
- K. Wakita: Community structure anlaysis - fixing unbalanced merging and significantly improved the scalability.
- Louvain method - The state-of-the-art method in the paradigm of fast, hierachicaly modularity optimization. It is faster and more accurate.
- YYiki: Community structure
- Wikipedia: Heap
- Wikipedia: Dijkstra's algorithm
|
Ali |
Modularity |
1/24 |
Required reading:
Further reading:
- A. Arenas et al., Analysis of the structure of complex networks at different resolution levels, New Journal of Physics, 2008.
- J.M. Kumpula et al., Limited resolution in complex network community detection with Potts model approach, EPJB, 2007.
- J. Ruan and W. Zhang, Identifying network communities with a high resolution, PRE, 2008.
- U. Brandes et al., Maximizing modularity is hard, arXiv, 2006
- R. Lambiotte et al., Laplacian dynamics and multiscale modular structure in networks, arXiv, 2009.
- R. Guimerà and L.A.N. Amaral, Functional cartography of complex metabolic networks, Nature, 2004 - can we categorize the functional role of nodes based on community structure?
- J.P. Bagrow, Are communities just bottlenecks? Trees and treelike networks have high modularity,arXiv, 2012 - Trees have high modularity.
Exercise #1 (one week): download American
college footbal network data from here.
Load the network into memory and calculate the degree
distribution, clustering coefficient, and average path length.
Repeat it with WWW data from here.
|
Huizi |
Scale-free networks |
1/26 |
Required reading:
Further reading:
- M.E.J. Newman, Power laws, pareto distributinos and Zipf's law, Contemporary physics, 2005 - A nice overview of power-law phenomena and mechanisms
- A. Clauset et al., Power-law distributions in empirical data, SIAM Review, 2009.
- M. Mitzenmacher, A brief history of generative models for power law and lognormal distributions, Internet Mathematics, 2004.
- A.-L. Barabási et al., Mean-field theory for scale-free random networks, Physica A, 1999.
- R. Cohen and S. Havlin, Scale-Free Networks Are Ultrasmall, PRL, 2003.
- M.E.J. Newman et al., Random graphs with arbitrary degree distributions and their applications, PRE, 2001 - Another type of graph model.
- K.-I. Goh et al., Universal Behavior of Load Distribution in Scale-Free Networks, PRL, 2001 - So-called 'static scale-free mode'.
- K. Klemm and V.M. Eguiluz, Highly clustered scale-free networks, PRE, 2002 - You can add more clustering by limiting the 'memory' of nodes.
- P. Holme and B.J. Kim, Growing Scale-Free Networks with Tunable Clustering, PRE, 2002 - Another way to achieve high clustering
- B.J. Kim et al., Path finding strategies in scale-free networks, PRE, 2002.
|
Alex |
Overlapping communities |
1/31 |
Required reading:
Further reading:
- I. Derény et al., Clique percolation in random networks, PRL, 2005 - Analytical study on the properties of clique percolation in random networks.
- J.M. Kumpula et al., A sequential algorithm for fast clique percolation, PRE, 2008 - An improved algorithm of clique percolation. Also provide natural generalization to weighted networks.
- Python implemention of the SCP algorithm - Python source code for the sequential algorithm.
- S. Lehmann et al., Bi-clique communities PRE, 2008 - Extension of clique percolation to bi-partite graphs
- C. Lee et al., Detecting highly overlapping community structure by greedy clique expansion, arXiv, 2010 - Another approach based on cliques.
- A. Lázár et al., Modularity measure of networks with overlapping communities, arXiv, 2009
- V. Nicosia et al., Extending the definition of modularity to directed graphs with overlapping communities, J. Stat. Mech., 2009
- C. Song et al., Self-similarity of complex networks, Nature, 2005
- C. Song et al., Origins of fractality in the growth of complex networks, Nature, 2006.
|
Abhik |
Web |
2/2 |
Required reading:
Further reading:
- D. Gibson et al., Inferring
web communities from link topology, Proc. 9th ACM
Conference on Hypertext and Hypermedia, 1998
- S. Chakrabarti et al, Automatic
resource list compilation by analyzing hyperlink structure
and associated text. , WWW'98
- L. Li et al., Improvement
of HITS-based Algorithms on Web Documents,
WWW'02
- S. Chakrabarti et al., Hypersearching
the web, Scientific American, 1999
|
Shenshen |
2/7 |
Required reading:
Further reading:
- Wikipedia:
MapReduce
- MapReduce
- Wikipedia:
bigtable
- Bigtable
- A.N. Langville and C.D. Meyer, Google's
PageRank and Beyond: The Science of Search Engine
Rankings - A book on pagerank.
- P. Chen et al., Finding
Scientific Gems with Google, J. Informet.,
2007 - "Let's use page rank for citation network."
- S. Fortunato et al., On
Local Estimations of PageRank: A Mean Field Approach,
Internet Math., 2007
- G. Ghosal and A.-L. Barabási, Ranking
stability and super-stable nodes in complex networks,
Nature Communications, 2011 - Given a degree
distribution, how stable the pagerank is? Also check out the
references.
- S.-W. Son et al., PageRank and
rank-reversal dependence on the damping factor,
arXiv, 2012
- A. Cheng and E. Friedman, Manipulability
of PageRank under Sybil Strategies, NetEcon06
- Is the pagerank robust against malicious manupulation?
|
Lilian |
Overlapping communities, line
graph |
2/9 |
Required reading:
Further reading:
- T.S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities, PRE, 2009 - Independently developed line-graph based approach.
- T.S. Evans, Clique graphs and overlapping communities, Journal of Statistical Mechanics, 2010 - Higher order generalization
- B. Ball et al., Efficient and principled method for detecting communities in networks, PRE, 2011 - Generative model for link communities
- J. Parkkinen et al., A block model suitable for sparse graphs, 7th International Workshop on Mining and Learning with Graphs, 2009 - Machine learning approach
|
Jaehong |
Epidemic spreading |
2/14 |
Required reading:
Further reading:
- F. Liljeros et al, The Web of
Human Sexual Contacts, Nature, 2001
- M.E.J. Newman, Spread
of epidemic disease on networks, PRE,
2002
- R. Pastor-Satorras and A. Vespignani, Epidemic
dynamics and endemic states in complex networks,
PRE, 2001
- R.M. May and A.L. Lloyd, Infection
dynamics on scale-free networks, PRE, 2001
- A.L. Lloyd and R.M. May, How
Viruses Spread Among Computers and People,
Science, 2001
- R. Pastor-Satorras and A. Vespignani, Epidemic
dynamics in finite size scale-free networks,
PRE, 2002
- M. Barthélemy et al, Velocity
and Hierarchical Spread of Epidemic Outbreaks in Scale-Free
Networks, PRL, 2004
- M. Boguña et al, Absence
of epidemic threshold in scale-free networks with degree
correlations, PRL, 2003
|
Varsha |
Robustness |
2/16 |
Required reading:
Further reading:
- H. Jeong et al., Lethality and centrality in protein networks, Nature, 2001.
- R. Cohen et al., Resilience of the internet to random breakdowns, PRL, 2000.
- R. Cohen et al., Breakdown of the internet under intentional attack, PRL, 2001.
- DS Callaway et al., Network robustness and fragility: percolation on random graphs, PRL, 2000.
- H. Kitano, Biological robustness, Nature Review Genetics, 2004.
- DJ. Watts, A simple model of global cascades on random networks, PNAS, 2001.
|
Varsha |
Project proposal paper due |
2/21 | Project proposal presentations | |
Guest lectures |
2/23 |
Guest lecture: Johan Bollen | |
2/28 |
Guest lecture:
David Crandall, "Reconstructing the world from social photo-sharing websites"
|
|
3/1 |
Guest lecture: Apu Kapadia, "Privacy in
Social Networks: From Drunk Tweeting to Anonymous Counseling"
- Huina Mao, Xin Shuai, and Apu Kapadia, Loose
Tweets: An Analysis of Privacy Leaks on Twitter, WPES'11
- Shirin Nilizadeh, Naveed Alam, Nathaniel Husted, and Apu
Kapadia, Pythia:
A Privacy Aware, Peer-to-Peer Network for Social
Search, WPES '11
|
|
Random graphs |
3/6 |
Required reading:
Further reading:
|
YY |
3/8 |
Required reading:
Further reading:
- YY Ahn et al., Epidemic
dynamics of two species of interacting particles on
scale-free networks, PRE, 2006.
- S Funk and VAA Jansen, Interacting
epidemics on overlay networks, PRE, 2010.
- N Masuda and N Konno, Multi-state
epidemic processes on complex networks, J. Theo.
Biol., 2006.
- B Karrer and MEJ Newman, Competing
epidemics on complex networks, PRE, 2011.
|
Lilian |
3/13 | No class (spring recess) |
3/15 | No class (spring recess) |
Random walk and communities |
3/20 |
Required reading:
Further reading:
- code
- Huffman coding
- M. Rosvall and CT Bergstrom, An information-theoretic framework for resolving community structure in complex networks, PNAS, 2006
- M. Rosvall and CT Bergstrom, Mapping change in large networks, PLoS One, 2010.
- M. Rosvall et al., The map equation, 2009
- M. Rosvall and CT Bergstrom, Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems, PLoS One, 2011
- AV Esquivel and M. Rosvall, Compression of Flow Can Reveal Overlapping-Module Organization in Networks, PRX, 2011
|
Dimitar |
Project progress report due |
Epidemic spreading (immunization) |
3/22 |
Required reading:
Further readings:
- R. Cohen et al., Efficient
Immunization Strategies for Computer Networks and
Populations, PRL, 2003
- R Pastor-Satorras and A Vespignani, Immunization
of complex networks, PRE, 2002.
- Z Dezső and A-L Barabási, Halting
viruses in scale-free networks, PRE, 2002.
- J Leskovec et al., Cost-effective
outbreak detection in networks, KDD'07
- Y Chen et al., Finding
a Better Immunization Strategy, PRL,
2008.
|
YY |
Metabolic networks |
3/27 |
Required Readings
Further reading:
- Wikipedia: Flux
balance analysis
- JD Orth et al., What
is flux balance analysis?, Nature Biotech",
2010.
- Y Shen et al., Blueprint
for antimicrobial hit discovery targeting metabolic
networks, PNAS, 2010.
- U Alon, An
introduction to systems biology
- R Guimerà, Functional
cartography of complex metabolic networks,
Nature, 2005.
- H Kitano, Biological
robustness, Nature Review Genetics, 2004.
- E Almaas, Global
organization of metabolic fluxes in the bacterium
Escherichia coli, Nature, 2004.
- EF Keller, Revisiting
"scale-free" networks, BioEssays, 2005.
- A-L Barabási and ZN Oltvai, Network
biology: understanding the cell's functional
organization, Nature Review Genetics,
2004.
|
Shantanu |
Degree correlation |
3/29 |
Required reading
Further readings
- MEJ Newman, Assortative
mixing in networks, PRL, 2002.
- MEJ Newman and J. Park, Why social
networks are different from other types of networks,
PRE, 2003.
- V. Colizza et al., Detecting
rich-club ordering in complex networks, Nature
Physics, 2006.
- J. Park and MEJ Newman, Origin
of degree correlations in the Internet and other
networks, PRE, 2003.
- M. Boguña and R. Pastor-Satorras, Epidemic
spreading in correlated complex networks, PRL,
2002.
- M Boguña and R. Pastor-Satorras, Class
of correlated random networks with hidden variables,
PRE, 2003.
- M Catanzaro et al., Generation
of uncorrelated random scale-free networks,
PRE, 2005.
- J Park and MEJ Newman, Origin
of degree correlations in the Internet and other
networks, PRE, 2003.
- A Vázquez and Y Moreno, Resilience
to damage of graphs with degree correlations,
PRE, 2003.
- R Milo et al., On the uniform
generation of random graphs with prescribed degree
sequences, arXiv, 2004.
- M Catanzaro et al., Assortative
model for social networks, PRE, 2004.
|
Ian |
Protein-Protein interaction networks |
4/3 |
Required reading:
Further reading:
- H Jeong et al., Lethality
and centrality in protein networks, Nature,
2001.
- J-F Rual et al., Towards
a proteome-scale map of the human protein–protein
interaction network, Nature, 2005.
- JDJ Han et al., Evidence
for dynamically organized modularity in the yeast
protein–protein interaction network, Nature,
2004.
- V Sprin and LA Mirny, Protein
complexes and functional modules in molecular networks,
PNAS, 2003.
- K-I Goh et al., The
human disease network, PNAS, 2007.
- M Costanzo et al., The
Genetic Landscape of a Cell, Science,
2010.
- A-L Barabási et al., Network
medicine: a network-based approach to human disease,
Nature Review Genetics, 2011.
- M Vidal et al., Interactome
networks and human disease, Cell, 2011.
- Arabidopsis Interactome Mapping Consortium, Evidence
for Network Evolution in an Arabidopsis Interactome
Map, Science, 2011.
- AL Hopkins, Network
pharmacology: the next paradigm in drug discovery,
Nature Chemical Biology, 2008.
- MA Yildirim et al., Drug-target
network, Nature Biotech., 2007.
- A Vazquez et al., Global
protein function prediction from protein-protein
interaction networks, Nature Biotech.,
2003.
|
Jaehong |
Social contagion |
4/5 |
Required reading:
Further reading:
- W Goffman and VA Newill, Generalization
of Epidemic Theory: An Application to the Transmission of
Ideas, Nature, 1964.
- DJ Daley and DG Kendall, Epidemics
and Rumours, Nature, 1964.
- M Granovetter, Threshold
Models of Collective Behavior, American Journal of
Sociology, 1978.
- DJ Watts, A simple
model of global cascades on random networks,
PNAS, 2001.
- L Backstrom et al., Group
formation in large social networks: membership, growth, and
evolution, KDD '06.
- D Centola and M Macy, Complex
contagions and the weakness of long ties, Americal
Journal of Sociology, 2007.
- DM Romero et al., Differences
in the mechanics of information diffusion across topics:
idioms, political hashtags, and complex contagion on
twitter, WWW '11.
|
Varsha |
Project progress report due |
4/10 |
Required readings:
Further readings:
- NA Christakis and JH Fowler, The
Collective Dynamics of Smoking in a Large Social
Network, NEJM, 2008.
- JH Fowler and NA Christakis, Dynamic
spread of happiness in a large social network: longitudinal
analysis over 20 years in the Framingham Heart Study,
BMJ, 2008.
- JH Fowler and NA Christakis, Cooperative
behavior cascades in human social networks,
PNAS, 2010.
- NA Christakis and JH Fowler, Social Contagion
Theory: Examining Dynamic Social Networks and Human
Behavior
- R Lyons, The
Spread of Evidence-Poor Medicine via Flawed Social-Network
Analysis
- CR Chalizi and AC Thomas, Homophily and
Contagion Are Generically Confounded in Observational
Social Network Studies
|
Abhik |
4/12 |
Required reading:
Further readings:
- T Łuczak, Size and
connectivity of the k-core of a random graph,
Discrete Mathematics, 1991.
- JI Alvarez-Hamelin et al., Large
scale networks fingerprinting and visualization using the
k-core decomposition, Adv Neural Inf Process
Syst, 2006.
- L Backstrom et al., Group
formation in large social networks: membership, growth, and
evolution, KDD '06.
- S Carmi et al., A
model of Internet topology using k-shell decomposition,
PNAS, 2007.
- E Sun et al., Gesundheit!
modeling contagion through facebook news feed,
ICWSM '09.
|
Dimitar |
Geography and social connection |
4/17 |
Required reading:
Further readings:
- DJ Crandall et al., Inferring social ties from geographic coincidences, PNAS, 2010.
- Z Cheng et al., You are where you tweet: a content-based approach to geo-locating twitter users, CIKM '10
- S Scellato et al., Distance matters: geo-social metrics for online social networks, WOSN '10
- Z Cheng et al., Exploring Millions of Footprints in Location Sharing Services, ICWSM '11
- A Noulas et al., An Empirical Study of Geographic User Activity Patterns in Foursquare, ICWSM '11
- S Scellato et al., Socio-spatial Properties of Online Location-based Social Networks, ICWSM '11
- M Barthélemy, Spatial networks, Physics Reports, 2011.
- P Expert et al., Uncovering space-independent communities in spatial networks, PNAS, 2011.
- JP Onnela et al., Geographic Constraints on Social Network Groups, PLOS ONE, 2011.
|
Shenshen |
Review |
4/19 |
Required readings:
- A-L Barabási, The network takeover, Nature Physics, 2012.
- MEJ Newman, Communities,
modules and large-scale structure in networks,
Nature Physics, 2012.
- A. Vespignani, Modelling
dynamical processes in complex socio-technical systems,
Nature Physics, 2012.
|
YY |
Final paper due |
4/24 | Project presentation | |
4/26 | Project presentation | |
Performing a publishable research project (and publish) on network science.
.
The progress report will be a draft of the final paper. I can always
discuss about the project with you independent of the progress report.
6-10 pages, two column. You can use a generic CS conference format or
other reasonable journal/conference formats.
Prepare 10 minute presentation about your work.
The course structure (paper review - presentation - group discussion)
is mostly based on
's method.
You need to submit a short review of the papers by the midnight before
the class (e.g. by Monday night for the Tuesday's readings).
The review for each paper should consists of
For each of the points, just list them and add several supporting
arguments for each of them.
Assigned moderators will make a brief (~ 5 minutes) presentation about
the premises and the results of the paper. The essential elements in
the presentation are:
The principles of academic honesty and ethics will be enforced. Any
cases of academic misconduct (cheating, fabrication, plagiarism, etc)
will be thoroughly investigated and immediately reported to the
School and the Dean of Students.
You should actively discuss with others, but you should write your
own report and you should not read others' review. You should credit
all the sources (discussion with other students, using some
softwares, etc).