Skip to content
/ netpy Public
forked from lovre/netpy

NetPy '19: Introduction to Network Analysis in Python

Notifications You must be signed in to change notification settings

reicast/netpy

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

62 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

NetPy '19: Introduction to Network Analysis in Python

Workshop instructor

Asst. Prof. Lovro Šubelj, PhD, University of Ljubljana

Workshop schedule

Tuesday, 10th December 2019 at 3:30 PM (4 hours with breaks)

Workshop location

Lecture room 3 at UL FRI, Večna pot 113, Ljubljana, Slovenia

Materials and forum
High-level description

The workshop is primarily aimed at Python programmers, either academics, professionals or students, that wish to learn the basics of modern network science and practical analyses of complex real networks, such as social, information and biological networks. Familiarity with the basics of probability theory, statistics and linear algebra is strongly encouraged. The workshop is based on masters level course Network Analysis offered at University of Ljubljana, Faculty of Computer and Information Science.

Recommended prerequisites

It is recommended that attendees bring a laptop with working installation of Python, NetworkX and CDlib packages, and necessary dependencies. Alternatively, you can work with any other network analysis package such as igraph, graph-tool or SNAP.py. Finally, for the purposes of visualization of smaller networks, it is recommended to have working installation of some network analysis software such as Gephi or visone.

Tentative syllabus
  • Challenge: Warmup Guimera's four knights challenge (10 min)
  1. From classical graph theory to modern network science (30 min)
  2. Large-scale structure of real networks and graph models (50 min)
  3. Measures of node importance and link analysis algorithms (50 min)
  4. Network community, core-periphery and other structures (50 min)
  5. Network-based mining, visualization and some applications (50 min)
  • Hands-on: Abstraction, centrality, communities, mining, visualization etc.
Networks data

All networks are available in Pajek, edge list in LNA formats.

Let's start with Guimera's four knights challenge

Tentative duration

5+5 min

Challenge description

To be revealed in class =)

4knights

1. Classical graph theory → modern network science

Tentative duration

20+10 min

Brief description

Introduction of networks and selected motivational examples. From classical graph theory to social network analysis and modern network science. Network perspectives in different fields of science.

transportation

Lecture slides
Book chapters
Selected must-reads
  • Barabási, A.-L., The network takeover, Nat. Phys. 8(1), 14-16 (2012).
  • Motter, A.E. & Yang, Y., The unfolding and control of network cascades, Phys. Today 70(1), 33-39 (2017).
  • Cramer, C., Porter, M.A. et al., Network Literacy: Essential Concepts and Core Ideas (Creative Commons Licence, 2015).
Selected papers
  • Newman, M.E.J., The physics of networks, Phys. Today 61(11), 33-38 (2008).
  • Cimini, G., Squartini, T. et al., The statistical physics of real-world networks, Nat. Rev. Phys. 1(1), 58-71 (2019).
  • Newman, M.E.J., Communities, modules and large-scale structure in networks, Nat. Phys. 8(1), 25-31 (2012).
  • Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys. 8(1), 32-39 (2012).
  • Hegeman, T. & Iosup, A., Survey of graph analysis applications, e-print arXiv:180700382v1, pp. 23 (2018).
  • Hidalgo, C.A., Disconnected, fragmented, or united? A trans-disciplinary review of network science, Appl. Netw. Sci. 1, 6 (2016).

2. Large-scale network structure and graph models

Tentative duration

30+20 min

Brief description

Classical graph theory and modern network analysis. Random graphs, scale-free and small-world network models, and real network structure. Network representations, data formats and repositories.

smallworld

Lecture slides
Hands-on analysis
Networks data
Book chapters
Selected must-reads
Selected papers
  • Erdős, P. & Rényi, A., On random graphs I, Publ. Math. Debrecen 6, 290-297 (1959).
  • Milgram, S., The small world problem, Psychol. Today 1(1), 60-67 (1967). Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
  • Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
  • Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
  • Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
  • Albert, R., Jeong, H. & Barabási, A.-L., Error and attack tolerance of complex networks, Nature 406(6794), 378-382 (2000).
  • Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
  • Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
  • De Domenico, M. & Arenas, A., Modeling structure and resilience of the dark network, Phys. Rev. E 95(2), 022313 (2017).
  • Broido, A.D. & Clauset, A., Scale-free networks are rare, Nat. Commun. 10(1), 1017 (2019).
  • Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).
  • Holme, P., Rare and everywhere, Nat. Commun. 10(1), 1016 (2019).

3. Measures of node importance and link analysis

Tentative duration

30+20 min

Brief description

Node importance and measures of centrality, i.e. clustering coefficients, spectral, closeness and betweenness centrality, and link analysis algorithms. Link importance and measures of bridging, i.e. betweenness centrality, embeddedness and topological overlap.

centrality

Lecture slides
Hands-on analysis
Networks data
Book chapters
Selected must-reads
  • Jeong, H., Mason, S.P. et al., Lethality and centrality in protein networks, Nature 411, 41-42 (2001).
  • Jensen, P., Morini, M. et al., Detecting global bridges in networks, J. Complex Netw. 4(3), 319-329 (2015).
  • Tong, H., Faloutsos, C. & Pan, J.-Y., Fast random walk with restart and its applications, In: Proceedings of ICDM ’06 (Washington, DC, USA, 2006), pp. 613-622.
Selected papers
  • Freeman, L., A set of measures of centrality based on betweenness, Sociometry 40(1), 35-41 (1977).
  • Bonacich, P., Power and centrality: A family of measures, Am. J. Sociology 92(5), 1170-1182 (1987).
  • Kleinberg, J., Authoritative sources in a hyperlinked environment, J. ACM 46(5), 604-632 (1999).
  • Franceschet, M. & Bozzo, E., A theory on power in networks, e-print arXiv:1510.08332v2, pp. 19 (2016).
  • Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
  • Berkhin, P., A survey on PageRank computing, Internet Math. 2(1), 73-120 (2005).

4. Clusters of nodes and network mesoscopic structure

Tentative duration

30+20 min

Brief description

Network community, core-periphery and other mesoscopic structures. Graph partitioning, community detection, blockmodeling, stochastic block models and core-periphery detection.

community

Lecture slides
Hands-on analysis
Networks data
Book chapters
Selected must-reads
Selected papers

5. Network-based mining, visualization and applications

Tentative duration

30+20 min

Brief description

Network-based node clustering, classification and regression. Force-directed node layout and network visualization. Selected applications of network analysis (i.e. automobile insurance fraud and historical development of science).

collisions

Lecture slides
Hands-on analysis
Networks data
Selected must-reads
  • Grover, A. & Leskovec, J., node2vec, In: Proceedings of KDD ’16 (San Francisco, CA, USA, 2016), pp. 855-864.
  • Zanin, M., Papo, D. et al., Combining complex networks and data mining: Why and how, Phys. Rep. 635, 1-44 (2016).
  • Ma, K.-L. & Muelder, C.W., Large-scale graph visualization and analytics, Computer 46(7), 39-46 (2013).
Selected papers
  • Getoor, L. & Diehl, C.P., Link mining: A survey, SIGKDD Explor. 7(2), 3–12 (2005).
  • Getoor, L., Friedman, N. et al., Learning probabilistic models of link structure, J. Mach. Learn. Res. 3, 679–707 (2002).
  • Neville, J. & Jensen, D., Iterative classification in relational data, In: Proceedings of SRL ’00 (Austin, TX, USA, 2000), pp. 13–20.
  • Macskassy, S.A. & Provost, F., Classification in networked data: A toolkit and a univariate case study, J. Mach. Learn. Res. 8, 935-983 (2007).
  • Bhagat, S., Cormode, G. & Muthukrishnan, S., Node classification in social networks, e-print arXiv:1101.3291v1, pp. 37 (2011).
  • Šubelj, L., Exploratory and predictive tasks of network community detection, In: Proceedings of NetSci '15 (Zaragoza, Spain, 2015), p. 1.
  • Hric, D., Peixoto, T.P. & Fortunato, S., Network structure, metadata and the prediction of missing nodes, Phys. Rev. X 6(3), 031038 (2016).
  • Perozzi, B., Al-Rfou, R. & Skiena, S., DeepWalk, In: Proceedings of KDD ’14 (New York, NY, USA, 2014), pp. 701-710.
  • Figueiredo, D.R., Ribeiro, L.F.R. & Saverese, P.H.P., struc2vec, In: Proceedings of KDD ’17 (Halifax, Canada, 2017), pp. 1–9.
  • Peel, L., Graph-based semi-supervised learning for relational networks, In: Proceedings of SDM ’17 (Houston, TX, USA, 2017), pp. 1-11.

  • Eades, P., A heuristic for graph drawing, Congressus Numerantium 42, 146-160 (1984).
  • Kamada, T. & Kawai, S., An algorithm for drawing general undirected graphs, Inform. Process. Lett. 31(1), 7-15 (1989).
  • Fruchterman, T.M.J. & Reingold, E.M., Graph drawing by force-directed placement, Softw: Pract. Exper. 21(11), 1129-1164 (1991).
  • Kobourov, S.G., Spring embedders and force directed graph drawing algorithms, e-print arXiv:1201.3011v1, pp. 23 (2012).
  • Gibson, H., Faith, J. & Vickers, P., A survey of two-dimensional graph layout techniques for information visualisation, Infor. Visual. 12(3-4), 324-357 (2013).

About

NetPy '19: Introduction to Network Analysis in Python

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%