01.12.2019  Regular article  Ausgabe 1/2019 Open Access
Centrality in modular networks
 Zeitschrift:
 EPJ Data Science > Ausgabe 1/2019
Publisher’s Note
1 Introduction

Choose a standard centrality measure.

Compute the local network by removing all the intercommunity 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 intracommunity 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 intracommunity links predominate is densely connected and therefore it has a very welldefined 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 intercommunity links predominate has a noncohesive 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 Realworld networks

Social networks: Four Samples of the Facebook Network are used. The egoFacebook 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 EmailEucore^{1} 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: PowerGrid^{2} 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: GRQC^{a} (General Relativity and Quantum Cosmology) collaboration network has been collected from the eprint arXiv and covers scientific collaborations between authors of papers submitted to the General Relativity and Quantum Cosmology category. If an author i coauthored a paper with author j, the graph contains an edge from i to j. If the paper is coauthored by k authors this generates a completely connected (sub)graph on k nodes.
Network 
N

E
 〈k〉 
\(k_{\max }\)

C

\(\alpha _{\mathrm{th}}\)


egoFacebook  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 
EmailEucore  986  25,552  33.24  347  0.399  0.013 
Powergrid  4941  6594  2.66  19  0.107  0.092 
CRQC  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 Realworld networks
Network  egoFacebook  Powergrid  caGrQc  Princeton 

μ
 0.03  0.034  0.095  0.354 
Q
 0.834  0.934  0.86  0.753 
Network  EmailEucore  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  
Powergrid 
μ
 0.034  0.038 
Q  0.92  0.93  
Georgetown 
μ
 0.522  0.491 
Q  0.521  0.601 