- Docente: Giovanni Rossi
- Credits: 6
- SSD: SECS-P/10
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Computer Science (cod. 8028)
Learning outcomes
The purpose of this course is to examine current tools, methods and targets of complex network analysis. Attention is mostly placed on simple graphs, where edges are unordered pairs of vertices, although weighted graphs are also dealt with in some detail. In particular, [0-1]-ranged weights on edges are looked at in terms of random graphs, in that probabilistic models aimed at mirroring real complex networks are at the heart of network analysis. Students are expected to become familiar with quantities such as the degree distribution and the clustering coefficient, as well as with the expectation of these quantities in different random graphs. Developing from modularity maximization, graph clustering and community/module detection approaches are also covered to some extent, with an introduction to overlapping and/or fuzzy scenarios.
Course contents
- Simple graphs: path, cycle, vertex degree, connectivity, component, clique.
- [0,1]-weighted graphs as fuzzy edge subsets.
- Random graphs: the probability space of a fuzzy edge subset.
- Degree distribution and power-laws.
- Configuration model.
- Clustering coefficient.
- Graph clustering and community/module detection approaches.
- Modularity maximization and optimization-based methods.
Readings/Bibliography
- U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner. On modularity clustering. IEEE Trans. on Knowledge and Data Engineering, 20(2):172–188, 2007.
- A. E. Brower and W. H. Haemers. Spectra of Graphs. Springer, 2011.
- M. Chakrabarti, L. Heath, and N. Ramakrishnan. New methods to generate massive synthetic networks. arXiv, cs. SI:1705.08473 v1, 2017.
- R. Diestel. Graph Theory. Springer, 2010.
- S. Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75–174, 2010.
- A. Lancichinetti, S. Fortunato, and J. Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3):033015, 2009.
- A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs
for testing community detection algorithms. Physics Review E,
78(4):046110, 2008.
- Y. Li, Y. Shang, and Y. Yang. Clustering coefficients of large networks. Information Sciences, 382-383:350–358, 2017.
- S. Miyamoto, H. Ichihashi, and K. Honda. Algorithms for Fuzzy
Clustering. Springer, 2008.
- T. Nepusz, A. Petróczi, L. Négyessy, and F. Baszó. Fuzzy communities and the concept of bridgeness in complex networks. Physics Review E, 77(1):016107, 2008.
- M. E. J. Newman. The Structure and Function of Complex Networks.
SIAM Review, 45(2):167–256, 2003.
- M. E. J. Newman. Fast algorithm for detecting communities in
networks. Physics Review E, 69(6):066133, 2004.
- M. E. J. Newman. Modularity and community structure in networks. PNAS, 103:8577–8582, 2006.
- M. E. J. Newman. Random graphs with clustering. Physical Review
Letters, 103(5):058701(4), 2009.
- M. E. J. Newman, A.-L. Barabási, and D. J. Watts. The Structure and
Dynamics of Networks. Princeton University Press, 2006.
- M. E. J. Newman and J. Park. Why social networks are different from other types of networks. Physical Review E, 68(3):036122, 2003.
- S. E. Schaeffer. Graph clustering. Computer Sc. Rev., 1:27–64, 2007.
- M. C. Schmidt, N. F. Samatova, K. Thomas, and B.-H. Park. A scalable, parallel algorithm for maximal clique enumeration. Journal of Parallel and Distributed Computing, 69(4):417–428, 2009.
- J. Xie, S. Kelley, and B. K. Szymanski. Overlapping community
detection in networks: the state of the art and a comparative study. ACM Computing Surveys, 45(43):43:1–43:35, 2012.
- T. Yu and M. Liu. A linear time algorithm for maximal clique
enumeration in large sparse graphs. Information Processing Letters, 125:35–40, 2017.
- S. Zhang, R.-S. Wang, and X.-S. Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Phisica A, 374:483–490, 2007.
Teaching methods
Traditional classes.
Assessment methods
Final grades are determined by evaluating an individual work that each student must detail/propose in advance, toward a final examination in form of both (i) a written (paper-like) document, and (ii) a spoken presentation.
Teaching tools
https://networkx.github.io/
http://snap.stanford.edu/
Office hours
See the website of Giovanni Rossi