BIMSA >
BIMSA-HSE Joint Seminar on Data Analytics and Topology
Properties of real networks and centrality measures
Properties of real networks and centrality measures
Organizers
Speaker
Mikhail Tuzhilin
Time
Monday, May 5, 2025 8:00 PM - 9:00 PM
Venue
A6-101
Online
Zoom 468 248 1222
(BIMSA)
Abstract
This seminar is scheduled for Monday from 20:00 to 21:00(Beijing Time)/15:00 to 16:00(Moscow Time).
One of the most important questions in the network science is which characteristics differentiate artificial networks from real ones based on real experimental data. Centrality measures or shortly centralities play important role in this question. There are two main invariants that distinguish real networks from random ones: degree centrality and local clustering coefficient. For real networks, degree centrality obeys a power law, unlike the distribution of random networks (the so-called scale-free property). For small-world networks, the threshold of the average clustering coefficient and the average shortest path length differ from random ones (the small-world property).
There are many mathematical models that simulate these two properties. For example, the Watts-Strogatz network was the first mathematical network that satisfied the small-world property. However, this network is not scale-free. The Barabasi-Albert network is a scale-free network, but the average clustering coefficient is not large enough. These problems were solved in the network proposed by Boccaletti, Hwang, and Latora, which is scale-free and has a large average clustering coefficient.
In the first part of our talk, we will present theorems on the relationships between various centralities and other network characteristics. More precisely, we will show the relationships between stress, betweenness, radiality, and other small-world characteristics. We will present simple network properties in terms of local clustering centrality, where the average clustering coefficient is greater than the global clustering coefficient and vice versa. We will also show the case for a geodesic network where there exists a relationship between the average clustering coefficient and the average shortest path.
In the second part of our talk, we will present a new invariant for real networks, called ksi-centrality. We will show that this ksi-centrality not only distinguishes random networks from real ones, but also prove that it is related to the local clustering coefficient, the algebraic connectivity of the network, and the Cheeger constant. Moreover, Watts-Strogatz, Barabasi-Albert and Boccaletti, Hwang, and Latora networks are generally classified as random or artificial networks by this centrality, but there is a narrow set of parameters for which Watts-Strogatz and Barabasi-Albert networks have the same properties as real networks by this centrality. In this case, Watts-Strogatz and Barabasi-Albert networks have a more tree-like structure, like real networks.
One of the most important questions in the network science is which characteristics differentiate artificial networks from real ones based on real experimental data. Centrality measures or shortly centralities play important role in this question. There are two main invariants that distinguish real networks from random ones: degree centrality and local clustering coefficient. For real networks, degree centrality obeys a power law, unlike the distribution of random networks (the so-called scale-free property). For small-world networks, the threshold of the average clustering coefficient and the average shortest path length differ from random ones (the small-world property).
There are many mathematical models that simulate these two properties. For example, the Watts-Strogatz network was the first mathematical network that satisfied the small-world property. However, this network is not scale-free. The Barabasi-Albert network is a scale-free network, but the average clustering coefficient is not large enough. These problems were solved in the network proposed by Boccaletti, Hwang, and Latora, which is scale-free and has a large average clustering coefficient.
In the first part of our talk, we will present theorems on the relationships between various centralities and other network characteristics. More precisely, we will show the relationships between stress, betweenness, radiality, and other small-world characteristics. We will present simple network properties in terms of local clustering centrality, where the average clustering coefficient is greater than the global clustering coefficient and vice versa. We will also show the case for a geodesic network where there exists a relationship between the average clustering coefficient and the average shortest path.
In the second part of our talk, we will present a new invariant for real networks, called ksi-centrality. We will show that this ksi-centrality not only distinguishes random networks from real ones, but also prove that it is related to the local clustering coefficient, the algebraic connectivity of the network, and the Cheeger constant. Moreover, Watts-Strogatz, Barabasi-Albert and Boccaletti, Hwang, and Latora networks are generally classified as random or artificial networks by this centrality, but there is a narrow set of parameters for which Watts-Strogatz and Barabasi-Albert networks have the same properties as real networks by this centrality. In this case, Watts-Strogatz and Barabasi-Albert networks have a more tree-like structure, like real networks.