1 Introduction
-
Choose a standard centrality measure.
-
Compute the local network by removing all the inter-community links from the modular network.
-
Compute the Local component of the Modular centrality using the standard centrality.
-
Compute the global network by removing all the intra-community links from the modular network.
-
Compute the Global component of the Modular centrality using the standard centrality.
2 Related works
3 Modular centrality
3.1 Definitions
3.1.1 Local component of the Modular centrality
3.1.2 Global component of the Modular centrality
3.1.3 Modular centrality
3.2 Algorithm
3.3 Modular extensions of standard centrality measures
3.3.1 Modular Betweeness centrality
3.3.2 Modular Closeness centrality
3.3.3 Modular Eigenvector centrality
3.4 Toy example
Node ID | 4 | 11 | 18 | 22 | 1 | 2 | 3 | 16 | 5 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|---|---|
β
|
7
|
7
| 5 | 5 | 4 | 4 | 4 | 4 | 3 | 3 | 3 |
\(\beta _{L} \)
| 3 |
7
| 3 | 3 | 4 | 2 | 4 | 2 | 3 | 2 | 3 |
\(\beta _{G} \)
|
4
| 0 | 2 | 2 | 0 | 2 | 0 | 2 | 0 | 1 | 0 |
Node ID | 9 | 10 | 14 | 15 | 17 | 19 | 21 | 6 | 12 | 20 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|
β
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
\(\beta _{L} \)
| 2 | 3 | 2 | 3 | 3 | 3 | 3 | 1 | 2 | 2 | 1 |
\(\beta _{G} \)
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
3.5 Modular centrality ranking strategies
-
A community \(C_{k}\), where the intra-community links predominate is densely connected and therefore it has a very well-defined community structure. If an epidemic starts in such a cohesive community, it has more chance to stay confined than to propagate through the few links that allows to reach the other communities of the network. In this case, priority must be given to local immunization. Consequently, more weight is given to the Local component of the Modular centrality \(\beta _{L}\) to target the most influential nodes in the community since it is well separated from the other communities of the network.
-
A community \(C_{k}\) where the inter-community links predominate has a non-cohesive community structure. It is more likely that an epidemic starting in this community diffuses to the other communities through the many links that it shares with the other communities. Consequently, more weight is given to the Global component of the Modular centrality measure \(\beta _{G}\) in order to target nodes that can propagate the epidemic more easily all over the network due to the loose community structure of \(C_{k}\).
4 Experimental setting
4.1 Dataset
4.1.1 Synthetic networks
Number of nodes | 4000 |
Average degree | 7 |
Maximum degree | 80 |
Exponent for the degree distribution | 2.8 |
Exponent for the community size distribution | 2 |
Mixing parameter | 0.1, 0.4, 0.7 |
Community size range | [15 200] |
4.1.2 Real-world networks
-
Social networks: Four Samples of the Facebook Network are used. The ego-Facebook network collected from survey participants using the Facebook app. [33] and the Facebook friendship network at 3 US universities (Caltech, Princeton, Georgetown) collected by Traud et al. [34]. Nodes represent individuals (survey participant or members of the University), and edges represent online friendship links between two individuals. In the University network, in order to obtain data that are relevant for the spread of epidemic infections, only the relationship of individuals who live in the same dormitory or study the same major are considered.
-
Communication network: The Email-Eu-core1 network has been generated using email data from a large European research institution. The dataset contains only communication between institution members. Each node corresponds to an email address and an edge is established between two nodes u and v, if at least one email has been exchanged between address u and address v.
-
Technological network: Power-Grid2 is a network containing information about the topology of the Western States Power Grid of the United States. An edge represents a power supply line. A node is either a generator, a transformer or a substation.
-
Collaboration network: GR-QCa (General Relativity and Quantum Cosmology) collaboration network has been collected from the e-print arXiv and covers scientific collaborations between authors of papers submitted to the General Relativity and Quantum Cosmology category. If an author i co-authored a paper with author j, the graph contains an edge from i to j. If the paper is co-authored by k authors this generates a completely connected (sub)graph on k nodes.
Network |
N
|
E
| 〈k〉 |
\(k_{\max }\)
|
C
|
\(\alpha _{\mathrm{th}}\)
|
---|---|---|---|---|---|---|
ego-Facebook | 4039 | 88,234 | 43.69 | 1045 | 0.605 | 0.009 |
Caltech | 620 | 7255 | 43.31 | 248 | 0.443 | 0.012 |
Princeton | 5112 | 28,684 | 88.93 | 628 | 0.298 | 0.006 |
Georgetown | 7423 | 162,982 | 90.42 | 1235 | 0.268 | 0.006 |
Email-Eu-core | 986 | 25,552 | 33.24 | 347 | 0.399 | 0.013 |
Power-grid | 4941 | 6594 | 2.66 | 19 | 0.107 | 0.092 |
CR-QC | 4158 | 13,428 | 5.53 | 81 | 0.529 | 0.059 |
4.2 SIR simulations
4.3 Evaluation criteria
5 Experimental results
5.1 Synthetic networks
5.1.1 Evaluation of the local and the global component of the Modular centrality
5.1.2 Evaluation of the ranking methods of the Modular centrality
5.2 Real-world networks
Network | ego-Facebook | Power-grid | ca-GrQc | Princeton |
---|---|---|---|---|
μ
| 0.03 | 0.034 | 0.095 | 0.354 |
Q
| 0.834 | 0.934 | 0.86 | 0.753 |
Network | Email-Eu-core | Caltech | Georgetown |
---|---|---|---|
μ
| 0.42 | 0.448 | 0.522 |
Q
| 0.569 | 0.788 | 0.662 |
5.2.1 Evaluation of the local and global component of the Modular centrality
5.2.2 Evaluation of the ranking methods of the Modular centrality
5.2.3 Comparisons with the alternative measures
5.2.4 Influence of the community detection algorithms
Network | Metric | Detection algorithm | |
---|---|---|---|
Louvain | Infomap | ||
Power-grid |
μ
| 0.034 | 0.038 |
Q | 0.92 | 0.93 | |
Georgetown |
μ
| 0.522 | 0.491 |
Q | 0.521 | 0.601 |