72677 - ANALISI DELLE RETI SOCIALI APPLICATA AD INTERNET

Scheda insegnamento

  • Docente Giovanni Rossi

  • Crediti formativi 6

  • SSD SECS-P/10

  • Modalità didattica Convenzionale - Lezioni in presenza

  • Lingua di insegnamento Italiano

  • Orario delle lezioni dal 26/09/2018 al 13/12/2018

Anno Accademico 2018/2019

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.

Programma/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 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