Stop Thinking, Just Do!

Sungsoo Kim's Blog

Structural Analysis and Visualization of Networks

tagsTags

29 April 2017

Article Source

Structural Analysis and Visualization of Networks

Outline

  1. Introduction to network science
  2. Power laws
  3. Models of network formation
  4. Structure, nodes and links analysis
  5. Network communities
  6. Evolving networks and link prediction
  7. Diffusion and random walks
  8. Epidemics on networks
  9. Diffusion of information
  10. Influence propagation

Module 3

Lectures

  1. [15.01.2015] Introduction to network science. [Lecture 1] [Video]
    Introduction to the complex network theory. Network properties and metrics.
  2. [20.01.2015] Power laws. [Lecture 2] [Video]
    Power law distribution. Scale-free networks.Pareto distribution, noramlization, moments. Zipf law. Rank-frequency plot.
  3. [27.01.2015] Random graphs. [Lecture 3] [Video]
    Erdos-Reni random graph model. Poisson and Bernulli distributions. Distribution of node degrees. Phase transition, gigantic connected component. Diameter and cluster coefficient. Configuration model
  4. [03.02.2015] Small world and dynamical growth models. [Lecture 4] [Video]
    Barabasi-Albert model. Preferential attachement. Time evolition of node degrees. Node degree distribution. Average path length and clustering coefficient. Small world model. Watts-Strogats model. Transition from ragular to random. Clustering coefficient and ave path lenght.
  5. [10.02.2015] Centrality measures. [Lecture 5] [Video]
    Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Katz status index and Bonacich centrality, alpha centrality Spearman rho and Kendall-Tau ranking distance.
  6. [17.02.2015] Link analysis. [Lecture 6 ] [Video]
    Directed graphs. PageRank, Perron-Frobenius theorem and algorithm convergence. Power iterations. Hubs and Authorites. HITS algorithm.
  7. [24.02.2015] Structural equivalence. [Lecture 7] [Video]
    Structural and regular equivalence. Similarity metrics. Correlation coefficient and cosine similarity. Assortative mixing and homophily. Modularity. Assortativity coefficient. Mixing by node degree. Assortative and disassortative networks.
  8. [03.03.2015] Network communitites. [Lecture 8] [Video]
    Cohesive subgroups. Graph cliques, k-plexes, k-cores. Network communities. Vertex similarity matrix. Similarity based clustering. Agglomerative clustering. Graph partitioning. Repeated bisection. Edge Betweenness. Newman-Girvin algorithm.
  9. [10.03.2015] Graph partitioning algorithms. [Lecture 9] [Video]
    Graph density. Graph pertitioning. Min cut, ratio cut, normalized and quotient cuts metrics. Spectral graph partitioning (normalized cut). Direct (spectral) modularity maximization. Multilevel recursive partitioning
  10. [17.03.2015] Community detection. [Lecture 10] [Video]
    Community detection algorithms. Overlapping communities. Clique percolation method. Heuristic methods. Label propagation. Fast community unfolding. Random walk based methods. Walktrap. Nibble.
  11. [24.03.2015] Student midterm exam presentations. [Video]

Labs

iPython notebooks:

  1. Introduction to iPython enviroment and NetworkX. Lab 1
  2. Power laws. Lab 2
  3. Random graphs. Lab 3
  4. Small world models. Lab 4
  5. Node centralities. Lab 5
  6. PageRank and HITS. Lab 6
  7. Structural similarity. Lab 7
  8. Dense Subgroups in Networks, Communities and Motif counting. Lab 8
  9. Community detection algorithms. Lab 9
  10. Community detection algorithms, part 2. Lab 10

Homeworks

  1. [20.01.2015, due: 28.01.2015]. Power laws. Homework 1
  2. [10.02.2015, due: 18.02.2015]. Network models. Homework 2
  3. [27.02.2015, due: 09.03.2015]. Centralities and assortativitiy coefficients. Homework 3
  4. [11.03.2015, due: 19.03.2015]. Community Detection Algorithms. Homework 4
  5. [17.03.2015, due: 24.03.2015]. FB or VK personal graph analysis. Midterm exam presentation.

Module 4

Lectures

  1. [31.03.2015] Diffusion on networks [Lecture 11] [Video]
    Random walks on graph. Stationary distribution. Physical diffusion. Diffusion equation. Diffusion on networks. Discrete Laplace operator, Laplace matrix. Solution of the diffusion equation. Normalized Laplacian.
  2. [07.04.2015] Epidemics [Lecture 12] [Video]
    Epidemic models: SI, SIS, SIR. Limiting cases. Basic reproduction number. Branching Galton-Watson process. Probability of epidemics.
  3. [14.04.2015] Epidemics on networks [Lecture 13] [Video] .
    Spread of epidemics on network. SI, SIS, SIR models. Epidemic threshold. Simulations of infection propagation.
  4. [21.04.2015] Social contagion and spread of information [Lecture 14] [Video]
    Information diffusion. Rumor spreading models. Homogenous and mean field models. Examples. Cascades and information propagation trees.
  5. [28.04.2015] Diffusion of innovation and influence maximization [Lecture 15] [Video]
    Diffusion of innovation. Independent cascade model. Linear threshold model. Influence maximization. Submodular functions. Finding most influential nodes in networks.
  6. [12.05.2015] Social learning [Lecture 16] [Video]
    Social learning in networks. DeGroot model. Reaching consensus. Influence vector. Social influence networks
  7. [19.05.2015] Label propagation on graph [Lecture 17] [Video1] [Video2]
    Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
  8. [26.05.2015] Link prediction [Lecture 18] [Video]
    Link prediction problem. Proximity measures. Scoring algorithms. Prediction by supervised learning. Performance evaluation.
  9. [02.06.2015] Spatial segregation [Lecture 19] [Video]
    Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
  10. [09.06.2015] Strategic network formation [Lecture 20]
    Economic models of networks. Course summary.

Labs

iPython notebooks:

  1. Random walk modeling. Lab 1
  2. Epidemics Lab 2
  3. Epidemics on networks. Lab 3
  4. Threshold models. Lab 4
  5. Social learning. Lab 5
  6. Node label and link prediction. Lab 6
  7. Segregation models. Lab 7

Projects

  1. Information and influence propagation in networks. Course Project 1
  2. Link prediction. Course Project 2

Reading material

    Lecture 1:
  • Albert-Laszlo Barabasi and Eric Bonabeau. Scale Free Networks. Scientific American, p 50-59, 2003
  • Mark Newman. The physics of networks. Physics Today,2008
  • Stanley Milgram. The Small-World Problem. Psychology Today, Vol 1, No 1, pp 61-67, 1967
  • J. Travers and S. Milgram. An Experimental Study of the Small World Problem. Sociometry, vol 32, No 4, pp 425-433, 1969
  • J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging Network. Proceedigs WWW 2008
  • L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna. Four Degrees of Separation. WebSci '12 Procs. 4th ACM Web Science Conference, pp 33-42, 2012

    • Lecture 2:
  • M. E. J. Newman. Power laws, Pareto distributions and Zipf’s law. Contemporary Physics 46(5), 323-351, 2005
  • A. Clauset, C.R. Shalizi, M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009
  • M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
  • M.L. Goldstein, S.A. Morris, and G.G. Yen. Problems with fitting to the power-law distribution , Eur. Phys. J. B 41, pp 255–258, 2004.
  • Chapter 18. Power Laws and Rich-Get-Richer Phenomena. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

    • Lecture 3:
  • P. Erdos and A. Renyi. On random graphs I. Publ. Math. Debrecen, 1959.
  • P. Erdos and A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
  • Chapter 12. Random graphs. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 4:
  • Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. . Nature 393:440-42, 1998.
  • AL Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286, 1999.
  • Chapter 14. Models of network formation. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
  • Chapter 20. The Small-World Phenomenon. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

    • Lecture 5:
  • Linton C. Freeman. Centrality in Social Networks. Conceptual Clarification. Social Networks, Vol 1, pp 215-239, 1978
  • Phillip Bonacich. Power and Centrality: A Family of Measures. American journal of sociology, Vol.92, pp 1170-1182, 1987.
  • Leo Katz A new status index derived from sociometric analysis . Psychometrika, 19, 39-43, 1953.
  • Phillip Bonacich, Paulette Lloyd, Eigenvector-like measures of centrality for asymmetric relations . Social Networks 23, 191–201, 2001
  • Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
  • Chapter 5. Centrality and Prestige. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994

    • Lecture 6:
  • Sergey Brin, Larry Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine, ,1998.
  • John M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Andrei Broder et all. Graph structure in the Web. Procs of the 9th international World Wide Web conference, 2000
  • Amy N. Langville and Carl D. Meyer, A Survey of Eigenvector Methods of Web Information Retrieval. 2004
  • David F. Gleich. PageRank beyond the Web arXiv:1407.5107, 2014
  • Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
  • Chapter 14. Link Analysis and Web Search. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

    • Lecture 7:
  • White, D., Reitz, K.P. Measuring role distance: structural, regular and relational equivalence. Technical report, University of California, Irvine, 1985
  • S. Borgatti, M. Everett. The class of all regular equivalences: algebraic structure and computations. Social Networks, v 11, p65-68, 1989
  • E. A. Leicht, P.Holme, and M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E 73, 026120, 200
  • G. Jeh and J. Widom. SimRank: A Measure of Structural-Context Similarity. Proceedings of the eighth ACM SIGKDD , p 538-543. ACM Press, 2002
  • M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a Feather: Homophily in Social Networks, Annu. Rev. Sociol, 27:415-44, 2001.
  • M. Newman. Mixing patterns in networks. Phys. Rev. E, Vol. 67, p 026126, 2003
  • M. D. Conover, J. Ratkiewicz, et al. Political Polarization on Twitter. Fifth International AAAI Conference on Weblogs and Social Media, 2011
  • N. Christakis and J. Fowler. The spread of obesity in a large social network over 32 years. Engl J Med v 357:370-379, 2007
  • Chapter 9. Structural Equivalence. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
  • Chapter 12. Network Positions and Roles. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
  • Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 8:
  • S. E. Schaeffer. Graph clustering. Comp. Sci. Rev., Vol. 1, p 27-64, 2007
  • S. Fortunato. Community detection in graphs . Physics Reports, Vol. 486, pp. 75-174, 2010
  • V. Batagelj, M. Zaversnik. An O(m) Algorithms for Cores Decomposition of Networks. 2003
  • M.E.J. Newman. Modularity and community structure in networks. PNAS Vol. 103, N 23, pp 8577-8582, 2006
  • Chapter 7. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 9:
  • M. Fiedler. Algebraic connectivity of graphs, Czech. Math. J, 23, pp 298-305, 1973
  • A. Pothen, H. Simon and K. Liou. Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal of Matrix Analysis, 11, pp 430-452, 1990
  • Bruce Hendrickson and Robert Leland. A Multilevel Algorithm for Partitioning Graphs, Sandia National Laboratories, 199
  • Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, N 8, pp 888-905, 2000
  • M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
  • B. Good, Y.-A. de Montjoye, A. Clauset. Performance of modularity maximization in practical contexts, Physical Review E 81, 046106, 2010
  • Chapter 11. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 10:
  • 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.
  • U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76 (3), 036106, 2007.
  • P. Pons and M. Latapy, Computing communities in large networks using random walks, Journal of Graph Algorithms and Applications, 10, 191-218, 2006.
  • V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech. P10008, 2008.
  • Daniel A. Spielman, Shang-Hua Teng. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on computing, Vol. 42, p. 1-26, 2013
  • R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.
  • J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Statistical properties of community structure in large social and information networks. In WWW 08: Procs. of the 17th Int. Conf. on World Wide Web, pages 695-704, 2008.

    • Lecture 11:
  • Lovasz, L. Random walks on graphs: a survey. In Combinatorics, Paul Erdos is eighty. pp. 353 – 397. Budapest: Janos Bolyai Math. Soc., 1993
  • Chung, Fan R.K. Spectral graph theory (2ed.). Chapter 1. Providence, RI: American Math. Soc., 1997
  • Daniel A. Spielman. Spectral Graph theory. Combinatorial Scientific Computing. Chapman and Hall/CRC Press. 2011
  • Chapter 6. Mathematics of networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 12:
  • H.W. Hethcote. The Mathematics of Infections Diseases. SIAM Review, Vol. 42, No. 4, pp. 599-653, 2000
  • Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

    • Lecture 13:
  • Matt. J. Keeling and Ken.T.D. Eames. Networks and Epidemics models Journal R. Soc. Interface, Vol 2, pp 295-307, 2005
  • G. Witten and G. Poulter Simulations of infections diseases on networks Computers in Biology and Medicine, Vol 37, No. 2, pp 195-205, 2007
  • M. Kuperman and G. Abramson Small World Effect in an Epidemiological Model., Phys. Rev. Lett., Vol 86, No 13, pp 2909-2912, 2001
  • Manitz J, Kneib T, Schlather M, Helbing D, Brockmann D. Origin Detection During Food-borne Disease Outbreaks - A Case Study of the 2011 EHEC/HUS Outbreak in Germany. PLoS Currents. 2014
  • Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
  • Chapter 21. Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

    • Lecture 14:
  • D.J. Daley and D.G. Kendall. Stochastic Rumours. J. Inst. Maths. Applics 1, 42-45, 1965.
  • A. Barrat, M. Barthelemy, A. Vespignani Eds. Dynamical processes on complex networks, Cambridge University Press 2008
  • Y. Moreno, M. Nekovee, A. Pacheco. Dynamics of rumor spreading in complex networks. Phys. Rev. E 69, 066130, 2004
  • M. Nekovee, Y. Moreno, G. Biaconi, M. Marsili. Theory of rumor spreading in complex social networks. Physica A 374, pp 457-470, 2007.
  • Luis M.A. Bettencours, A. Cintron-Arias, D.I. Kaiser, C. Castillo-Chavez. The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models. Physica A, 364, pp 513-536, 2006.
  • D. Liben-Nowell, Jon Kleinberg. Tracing in formation flow on a global scale using Internet chain-letter data. , PNAS vol 105, n 12, pp 4633-4638, 2008
  • J.L. Iribarren, E. Moro, Impact of Human Activity Patterns on the Dynamics of Information Diffusion, Phys. Rev. Letters, Vol 103, 038702, 2009
  • J. Leskovec, L. Adamic, B. Huberman, The Dynamics of Viral Marketing, EC 2006

    • Lecture 15:
  • Mark S. Granovetter. Threshold Models of Collective Behavior. American Journal of Sociology Vol. 83, No. 6, pp. 1420-1443, 1978.
  • H. Peyton Young. The Diffusion of Innovations in Social Networks. In L. E. Blume and S. N. Durlauf (eds.), The Economy as an Evolving Complex System III (2003)
  • D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.
  • D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
  • D. Kempe, J. Kleinberg, E. Tardos. Influential Nodes in a Diffusion Model for Social Networks. Lecture Notes in Computer Science, Eds C. Luis, I.Giuseppe et.al, 2005
  • S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
  • L.Backstrom, D. Huttenlocher, J. Kleinbrg, X. Lan, Group Formation in Large Social Networks: Membership, Growth and Evolution, In Proc. KDD 2006.
  • Chapter 19. Cascading Behavior in Neworks. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
  • Chapter 7. Diffusion through Networks. Matthew O. Jackson. "Social and Economic Networks".

    • Lecture 16:
  • M.H. DeGroot. Reaching a Consensus. Journal of the American Statistical Association, 1974, Vol 69, No 345
  • Roger L. Berger. A Necessary and Sufficient Condition for Reaching a Consensus Using DeGroot's Method. Journal of the American Statistical Association, Vol. 76, No 374, 1981, pp 415-418
  • Noah Friedkin, and Eugene C. Johnsen, Social Influence Networks and Opinion Change Advances in Group Processes 16:1-29, 1999
  • B. Golub and M. Jackson Naive Learning in Social Networks and the Wisdom of Crowds, Amer. Econ. J. Microeconomics, 2:1, pp 112-149, 2010
  • Chapter 8. Learning and Networks. Matthew O. Jackson. "Social and Economic Networks".

    • Lecture 17:
  • S. A. Macskassy, F. Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study. Journal of Machine Learning Research 8, 935-983, 2007
  • Bengio Yoshua, Delalleau Olivier, Roux Nicolas Le. Label Propagation and Quadratic Criterion. Chapter in Semi-Supervised Learning, Eds. O. Chapelle, B. Scholkopf, and A. Zien, MIT Press 2006
  • Smriti Bhagat, Graham Cormode, S. Muthukrishnan. Node classification in social networks. Chapter in Social Network Data Analytics, Eds. C. Aggrawal, 2011, pp 115-148
    • D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Scholkopf. Learning with local and global consistency. In NIPS, volume 16, 2004.
  • X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML, 2003.
  • M. Belkin, P. Niyogi, V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 7, 2399-2434, 2006

    • Lecture 18:
  • D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019–1031, 2007
  • R. Lichtenwalter, J.Lussier, and N. Chawla. New perspectives and methods in link prediction. KDD 10: Proceedings of the 16th ACM SIGKDD, 2010
  • M. Al Hasan, V. Chaoji, S. Salem, M. Zaki, Link prediction using supervised learning. Proceedings of SDM workshop on link analysis, 2006
  • M. Rattigan, D. Jensen. The case for anomalous link discovery. ACM SIGKDD Explorations Newsletter. v 7, n 2, pp 41-47, 2005
  • M. Al. Hasan, M. Zaki. A survey of link prediction in social networks. In Social Networks Data Analytics, Eds C. Aggarwal, 2011.

    • Lecture 19:
  • Thomas C. Schelling Dynamic Models of Segregation , Journal of Mathematical Sociology, Vol. 1, pp 143-186, 1971.
  • Arnaud Banos Network effects in Schellin's model of segregation: new evidences from agent-based simulations. Environment and Planning B: Planning and Design Vol.39, no. 2, pp. 393-405, 2012.
  • Giorgio Gagiolo, Marco Valente, Nicolaas Vriend Segregation in netwroks. Journal of Econ. Behav. & Organization, Vol. 64, pp 316-336, 2007.

    • Lecture 20:
  • Matthew O. Jackson. The Economics of Social Networks. California Institute of Technology, 2005.
  • Matthew O. Jackson. A Strategic Model of Social and Economic Networks. Journal of Economic Theory, Vol 71, pp 44-74, 1996.
  • Chapter 6. Strategic Network Formation. Matthew O. Jackson. "Social and Economic Networks".

Textbooks

Books

  • "Networks: An Introduction", Mark Newman. Oxford University Press, 2010.
  • "Social and Economic Networks", Matthew O. Jackson. Princeton University Press, 2010.
  • "Networks, Crowds, and Markets: Reasoning About a Highly Connected World." David Easley and John Kleinberg, Cambridge University Press 2010.
  • "Social Network Analysis. Methods and Applications." Stanley Wasserman and Katherine Faust, Cambridge University Press, 1994

Reviews

Collections

  • "The Structure and Dynamics of Networks". Eds.M. Newman, A.-L. Barabasi, D. Watts. Princeton University Press, 2006.
  • "Network Analysis". Eds. Ulrik Brandes, Thomas Erlebach. Lecture Notes in Computer Science. Springer, 2005
  • "Social Network Data Analysis. Ed. Charu C. Aggarwal. Springer, 2011

Software

Similar courses

comments powered by Disqus

Sungsoo Kim
Principal Research Scientist
sungsoo@etri.re.kr

about me
sungsoo's scoop
sungsoo's facebook