Social Network Analysis

The course is an introduction to the analysis of complex and social networks. It provides an entry point into an interdisciplinary field that combines Computer Science, Mathematics, and Physics to study networks arising from diverse domains such as telecommunications, biology, and social and economic systems.

Building on the fundamental knowledge of graph theory, the course makes use of available analytical and computational tools for interdisciplinary analyses. The syllabus aims to introduce students to the basic concepts and key results of graph theory and to demonstrate their application to problems across different fields. Special emphasis is placed on the study of those network characteristics that correspond to “social behavior”, as defined within each application domain.

By the end of the course, students are expected to have acquired the fundamental knowledge of graph theory, to be able to apply these concepts to the analysis of networks regardless of the application domain, and to make effective use of practical programming tools for analyzing network topologies of varying sizes and applications.

The course covers the fundamental concepts and definitions related to graphs and networks. After a brief introduction to graph theory (to provide a common foundation for students who have not attended a related course), the course continues with a variety of techniques for analyzing complex and social networks, using measures such as the clustering coefficient and centrality metrics. By examining the degree distribution of nodes, networks are categorized into five topological classes.

All of these concepts are then applied to important problems in the analysis of complex networks, such as community detection, personalized search, malware and information diffusion, and motif discovery. The course aims to expose students to both theoretical concepts and programming tools applied to real-world problems from different domains, thus fostering interdisciplinary skills and practical experience.

Weekly Schedule

Week 1:
Review of graph theory: basic definitions (graph, subgraph), paths, distances, cycles, adjacency matrix, eigenvalues/eigenvectors, isomorphism.

Week 2:
Review of graph theory: trees, graph representation, planar graphs, coloring, covering.

Week 3:
Trees – Social network analysis metrics: degree distribution, average path length, clustering coefficient.

Week 4:
Social network analysis metrics: centralities.

Week 5:
Complex network topologies: lattices, random graphs, random geometric graphs, small-world networks, scale-free networks.

Week 6:
Random walks on graphs.

Week 7:
Personalized search on the web – PageRank.

Week 8:
Community detection: spectral clustering, modularity maximization, Girvan–Newman.

Week 9:
Community detection: node2vec.

Week 10:
Link prediction in networks.

Week 11:
Recommendation systems based on network data.

Week 12:
Virus and malware propagation in networks.

Week 13:
News and rumor spreading in networks.

1. Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας.
2. ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ, ΣΤΑΥΡΟΣ ΝΙΚΟΛΟΠΟΥΛΟΣ, ΓΕΩΡΓΙΑΔΗΣ ΛΟΥΚΑΣ, ΠΑΛΗΟΣ ΛΕΩΝΙΔΑΣ
3. Graph Theory [electronic resource], Reinhard Diestel

Class lectures + term project

• Use of electronic lecture notes

• Teaching support through the e-class electronic platform

Written exam + term project