- Docente: Giovanni Rossi
- Crediti formativi: 6
- SSD: SECS-P/10
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea Magistrale in Informatica (cod. 8028)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente conosce le metodiche e gli strumenti della network analysis nei loro fondamentali teorici e nelle tipiche applicazioni in internet, con riferimento alla caratterizzazione ed alla modellizzazione dei fenomeni economici e sociali propri della rete. E' in grado di disegnare un protocollo di ricerca ed applicarlo a contesti reali, definendo le modalità di acquisizione e gestione dei dati, l'identificazione e l'esecuzione di misure di rete, l'interpretazione dei loro esiti, in modo integrato con esigenze di simulazione e supporto alla presa delle decisioni. Lo studente conosce inoltre l'uso dei principali software di analisi statistica e rappresentazione grafica delle reti.
Contenuti
- 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.
Testi/Bibliografia
- 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.
Metodi didattici
Lezioni frontali.
Modalità di verifica e valutazione dell'apprendimento
Il voto finale risulta dalla valutazione di un lavoro individuale, che ciascuno studente deve proporre e definire dettagliatamente in anticipo, in vista della verifica finale che si basa sia su uno scritto, sia su una presentazione orale.
Strumenti a supporto della didattica
https://networkx.github.io/
http://snap.stanford.edu/Orario di ricevimento
Consulta il sito web di Giovanni Rossi