

Fragmenting networks by targeting collective
influencers at a mesoscopic level

Teruyoshi Kobayashi
Naoki Masuda
June 2016
㻌
Discussion Paper No.1616

GRADUATE SCHOOL OF ECONOMICS
KOBE UNIVERSITY㻌ROKKO, KOBE, JAPANFragmenting networks by targeting collective inﬂuencers at amesoscopic level
Teruyoshi Kobayashi
Graduate School of Economics, Kobe University, Kobe, Japan
Naoki Masuda∗
Department of Engineering Mathematics, University of Bristol, Bristol, UK

Abstract
A practical approach to protecting networks against epidemic processes such as spreading of
infectious diseases, malware, and harmful viral information is to remove some inﬂuential nodes
beforehand to fragment the network into small components. Because determining the optimalorder to remove nodes is a computationally hard problem, various approximate algorithms havebeen proposed to eﬃciently fragment networks by sequential node removal. Morone and Makse
proposed an algorithm employing the non-backtracking matrix of given networks, which outperforms various existing algorithms. In fact, many empirical networks have community structure,compromising the assumption of local tree-like structure on which the original algorithm is based.
We develop an immunization algorithm by synergistically combining the Morone-Makse algorithmand coarse graining of the network in which we regard a community as a supernode. In this way,
we aim to identify nodes that connect diﬀerent communities at a reasonable computational cost.
The proposed algorithm works more eﬃciently than the Morone-Makse and other algorithms on
networks with community structure.
keywords: network; community structure; epidemics∗

Corresponding author: naoki.masuda@bristol.ac.uk

1

INTRODUCTION

Identiﬁcation of inﬂuential nodes in a network is a topic of interest in network analysis,
enjoying numerous applications. For example, a removal or immunization of an inﬂuential
node may suppress spreading of an infectious disease that may occur later. A viral information spreading campaign starting from an inﬂuential node may be more successful thana campaign starting from other nodes. There are various notions of inﬂuential nodes, as
evinced by a multitude of deﬁnitions of node’s centrality corresponding to the aforementioned and other applications [1]. Among them, a major criterion of the inﬂuential node isthat the removal of a node, or immunization, eﬃciently fragments the network into small
pieces. Because the problem of ﬁnding the minimal set of nodes to be immunized to fragment the network is NP-hard [2], various immunization algorithms to determine the orderof the nodes to be removed to realize eﬃcient fragmentation of the network have been proposed [2–12], sometimes with the constraint that the information about the network is only
partially available [6, 13–17]. Notably, although immunizing hubs (i.e., nodes with a large
degree) ﬁrst is intuitive and much better than randomly selecting nodes to be immunized[18–20], many immunization algorithms outperform the hub-ﬁrst immunization algorithm.
Morone and Makse proposed a scalable and powerful algorithm to sequentially remove
nodes and fragment the network into small components as early as possible [9]. Founded on
the message passing approach and theory of non-backtracking matrices, the method calculates the so-called collective inﬂuence (CI) for each node to rank the nodes for prioritization.
Their method, which is referred to as the CI algorithm, outperforms various other known
methods in model and empirical networks. In the present study, we propose a new CI-based
immunization algorithm that is designed to perform well when the network has community
structure.
The CI algorithm assumes that the given network is locally tree-like. In fact, a majorityof empirical networks are not locally tree-like. At a microscopic level, empirical networks
are usually clustered, i.e., full of triangles [1]. At a mesoscopic level, many networks arecomposed of communities such that links are dense within communities and sparse acrossdiﬀerent communities [21]. Although the CI algorithm also seems to work eﬃciently in loopy
networks unless loops are not excessive [9], the performance of the CI algorithm on networks
with community structure is unclear. Some extant immunization algorithms are explicitly2

or implicitly informed by community structure [4–6, 10, 15, 16, 22, 23]. The immunization algorithms using the betweenness centrality are eﬀective on networks with community
structure [6, 7, 16, 22, 23]. However, they are not scalable due to a high computational
cost of calculating the betweenness centrality [24]. For other immunization algorithms exploiting community structure of networks, their performance relative to the CI algorithm
is unknown in general [5, 10] or at least for networks with community structure [4, 9]. Yetother community-based immunization algorithms impose that only local information about
the network is available, mimicking realistic constraints [6, 15, 16]. This constraint naturally
limits the performance of an immunization algorithm.
We develop an immunization algorithm by formulating a CI algorithm for a coarse-grained
network, in which a node represents a community, and a weighted link represents the number of links between diﬀerent communities. We compare the performance of the proposed
algorithm with that of the CI algorithm [9], and the conventional algorithm targeting hubs
[18–20], and others [5, 10] when networks have community structure.

THEORY

Consider an undirected and unweighted network having N nodes. The aim of an immunization algorithm is to sequentially remove nodes to fragment the network as soon as
possible, i.e., with a small number of removed nodes.

Collective inﬂuence

The CI algorithm is based on the scoring of nodes according to the CI value [9]. The CI
of node i is deﬁned as
CI (i) = zi



zj ,

(1)

j∈∂Ball(i,)wherezi ≡ ki − 1,(2)

ki is the degree of node i, and ∂Ball(i, ) is the set of nodes at distance  from node i. When
 = 0, the CI is equivalent to the degree as long as the rank order is concerned.
3

The CI algorithm calculates the CI (i) value of all nodes and removes the node with thelargest CI value in one step. Then, the CI values of all the remaining nodes are recalculated,
and the same procedure is repeated.
In fact, we use the order of nodes to be removed determined above as a tentative order.
To improve the overall performance, we reorder the nodes by reinserting them as follows. We
start from the situation in which the fraction of nodes in the largest connected component(LCC) is equal to or less than 0.01 for the ﬁrst time. Then, we calculate for each removed
node i the number of components that node i connects if it is reinserted in the current
network. Next, we add back the node that connects the smallest number of connectedcomponents. We repeat this procedure until all the removed nodes are reinserted such thatthe initial network is restored.
The computation time of the CI algorithm is evaluated as follows [9]. The calculationof CI (i) requires O(1) time for one node, and hence O(N ) time for all nodes. Because
sorting the CI (i) values consumes O(N log N ) time, each step of the CI algorithm consumes
O(N log N ) time. Therefore, the total computation time until O(N ) nodes are removed isevaluated as O(N 2 log N ). However, by exploiting the fact that the CI values of only O(1)nodes are aﬀected by the removal of a single node, one can accelerate the same algorithmwith a max-heap data structure, yielding O(N log N ) total computation time [25].

Community-based collective inﬂuence

Community structure may make a network not locally tree-like. We propose an immunization algorithm by running a weighted-network variant of the CI algorithm on a coarse-grained
network in which a community constitutes a supernode. We ﬁrst run a community detection
algorithm. Denote by NC the number of communities and by Ã the NC × NC coarse-grained
weighted adjacency matrix whose (I, J) element is equal to the number of links that connect
communities I and J (I = J). We use lowercases (e.g., i, j) to denote individual nodes anduppercases (e.g., I, J) to denote supernodes, i.e., communities, throughout the text. The
diagonal elements of Ã are set to zero.
Assume that the coarse-grained network is locally tree-like. By taking into account thefact that the coarse-grained network is generally a weighted network, we deﬁne the CI of4community I in the coarse-grained network byCI (I) = zI

zJ ,(3)˜
J∈∂Ball(I,)˜
where ∂Ball(I,) denotes the set of the communities whose distance from community I isequal to  in the coarse-grained network.
We setzI ≡NCI  =1ÃII  − minÃII  .


(4)

IThis deﬁnition is analogous to zi ≡ ki − 1 in Eq. (1). With this deﬁnition of zI , the CI ofcommunity I is equal to zero when I has only one neighbor, as in the original CI [9, 26].
We setzJ ≡NCÃJJ  − ÃJJ −( ≥ 1),(5)J  =1

where J is a community that is at distance  from I, and J − is the community that is at
distance  − 1 from I and on the path between I and J (Fig. 1(a)). It should be noted thatzJ is equal to zero if J − is the only neighbor of J. It should also be noted that, when every
community consists of only one node in the original network, CI (i) = CI (i) for 1 ≤ i ≤ N .
Equation (5) is ill-deﬁned for  = 0. To be consistent with the original deﬁnition of the CI,
we deﬁne zJ ≡ zJ for  = 0. Then, CI0 (I) is large when node I has a large degree in thecoarse-grained network.
Let A = (Aij ) be the adjacency matrix of the original network. Equation (3) is rewritten
asCI (I) = zI˜i∈ community I I  ∈∂Ball(I,1)

i ∈I  AiiÃII 

zJ ,(6)˜
J∈∂Ball(I,)I + =I 

where I + is the community adjacent to I (hence distance one from I) through which J isreached from I (Fig. 1(b)). On the basis of Eq. (6), we deﬁne the community-based collectiveinﬂuence (CbCI) of node i, denoted by CbCI(i), asi ∈I  Aii
CbCI(i) = zIÃII  ˜
I ∈∂Ball(I,1)

zJ ,(7)˜
J∈∂Ball(I,)I + =I 

where node i belongs to community I. In Eq. (7), the importance of a node stems fromthree factors. First, CbCI(i) is proportional to zI , which is essentially the number of intercommunity links of the community to which i belongs. Second, CbCI(i) is large if I has
5many high-degree nodes at distance  in the coarse-grained network (i.e., sum of zJ ). Third,
CbCI(i) is large if node i has many inter-community links relative to the total number ofinter-community links that community I has (i.e., i ∈I  Aii /ÃII  ). We set  = 2 in thefollowing numerical simulations. When  = 2, I + in Eqs. (6) and (7) coincide with J − in
Eq. (5) (Fig. 1(b)).
We remove the node with the largest CbCI value. If there are multiple nodes withthe same largest CbCI value, we select the node having the largest degree. If there are
multiple nodes with the same largest CbCI and degree, we break the tie at random. Then,
we recalculate the CbCI for all remaining nodes, remove the node with the largest CbCI,
and repeat the same procedure until the size of the LCC becomes equal to or less than
0.01N . We further optimize the obtained order of node removal by reinsertion, as in the
CI algorithm. We use the coarse-grained network, not the original network, to inform thereinsertion process in the CbCI algorithm. In other words, the number of communities
that belong to the same component as the reinserted node is measured for each tentatively
reinserted node. We decide to reinsert the node whose presence connects the least numberof communities (Fig. 1(c)).
Given a partitioning of the network into communities, the calculation of CbCI(i) for one
node consumes O(1) time. Therefore, if we adapt the original implementation of the CI
algorithm [9] to the case of the CbCI, sorting of CbCI(i) dominates the computation time of
the CbCI algorithm. The time complexity of the CbCI algorithm is the same as that of the
CI algorithm in Ref. [9], i.e., O(N 2 log N ), if community detection is not a bottleneck. The
use of the max-heap data structure makes the CbCI algorithm run in O(N log N ) time if
NC = O(N ) such that the CbCI values of O(1) nodes are aﬀected by the removal of a single
node. Generally speaking, the CbCI algorithm with the max-heap data structure runs inO(N log N ) × O(N/NC ) = O((N 2 /NC ) log N ) time.
We use the following six algorithms for community detection: (i) Infomap [27, 28], requiring O(M ) time [21], where M is the number of links, and hence O(N ) time for sparse
networks; (ii) Walktrap, which requires O(N 2 log N ) for most empirical networks [29]; (iii)the label-propagation algorithm, requiring nearly linear time in N [30]; (iv) a fast greedy algorithm for modularity maximization, requiring O(N (log N )2 ) time for sparse networks [31];(v) modularity maximization based on simulated annealing, which is practical up to ≈ 104
nodes in the original paper [32] and time-consuming because modularity must be maximized
6

in a parameter-dependent manner [33]; (vi) the Louvain algorithm, which practically runsin O(N ) time [34]. The last three algorithms intend to maximize the modularity, denotedby Q. The ﬁrst three algorithms detect communities according to diﬀerent criteria.
Except for the simulated annealing algorithm, the computational cost is at most that for
the CbCI algorithm given the partitioning of the network, i.e., O(N 2 log N ). Therefore, if the
CbCI algorithm is naively implemented, community detection is not a bottleneck in termsof the computation time when any of these ﬁve community detection algorithms is used. If
NC = O(N ) and we implement the CbCI algorithm using the max-heap data structure, acommunity detection algorithm requiring more than O(N log N ) time presents a bottleneck.
In this case, the Infomap when the network is sparse (i.e., M = O(N )), label-propagation
algorithm, and Louvain algorithm retain O(N log N ) total computation time of the CbCI
algorithm. The total computation time with any of the other three community detection
algorithms is governed by that of the community detection algorithm.

RESULTSIn this section, we compare the performance of the CbCI algorithm with the CI and otherimmunization algorithms (see Methods) on two model networks and 12 empirical networks.
Let q be the fraction of removed nodes. The size of the LCC after qN nodes have been
removed, divided by N , is denoted by G(q).

Scale-free network models with and without community structure

We start by testing various immunization algorithms on a scale-free network model withbuilt-in community structure (Methods). We sequentially remove nodes from this network
according to each immunization algorithm and track the size of the LCC. We use the community structure imposed by the model to inform the CbCI and CbDI algorithms. The
results for a range of immunization algorithms are shown in Fig. 2(a). Both CbCI andCbDI algorithms considerably outperform the CI algorithm. The CbCI algorithm performs
better than the CbDI algorithm. The performance of the CbCI algorithm is close to the
Betweenness algorithm. It should be noted that the Betweenness algorithm, while eﬃcient,
is not scalable to larger networks.
7

Next, we consider a scale-free network without community structure, which is generated
by the original BA model with N = 5000 and k ≈ 12 (the parameters of the model are equal
to m0 = m = 6). We run the CbCI and CbDI strategies by applying a community detection
algorithm to the generated network although the BA model lacks community structure. In
fact, all but the label-propagation algorithm returns a partitioning result. The performanceof the diﬀerent immunization algorithms for this network is compared in Fig. 2(b). The CbCI
algorithm combined with Infomap or Walktrap outperforms the Degree and LSP algorithms.
The performance of the CbCI algorithm is close to that of the CI algorithm except in an
early stage of node removal. A diﬀerent community-based immunization algorithm, CbDI,
lacks this feature. This result suggests that the CbCI algorithm combined with Infomap or
Walktrap can work eﬃciently even when the network does not have community structure.
The results for the CbCI and CbDI algorithms combined with the other four community
detection algorithms are shown in Fig. S2(a). The ﬁgure suggests that the CbCI algorithm
combined with Infomap or Walktrap performs better than when it is combined with adiﬀerent community detection algorithm.

Empirical networks

In this section, we run the CbCI and other algorithms on the following 12 empirical networks with community structure. (i) Two networks of Autonomous Systems of the Internet
constructed by the University of Oregon Route Views project [35–37]: A node is an Autonomous System. The network collected on 2 January 2000 and that on 31 March 2001 arereferred to as AS-1 and AS-2, respectively. (ii) Pretty Good Privacy network (PGP) [38]:Two persons are connected by a link if they share conﬁdential information using the PGP
encryption algorithm on the Internet. (iii) World Wide Web (WWW) [39]: A network ofwebsites connected by hyperlinks, which is originally a directed network. (iv) Email-based
communication network at Kiel University (referred to as email-uni) [40]: E-mail sending
activity among students, which provides a directed link, recorded over a period of 112 days.
(v) Email-based communication network in Enron Corporation (email-Enron) [36, 41, 42]:
Two e-mail users in the data set are connected by an unweighted directed link if at least
one e-mail has been sent from one user to the other user. (vi) Collaboration networks
in General Relativity and Quantum Cosmology (CA-GrQc), Astro Physics, (CA-Astroph),8

and Condensed Matter, (CA-Condmat) categories [36, 43] and High Energy Physics – Phenomenology (CA-HepPh) and High Energy Physics – Theory (CA-HepTh) categories inarXiv [35, 36]. By deﬁnition, two authors are adjacent if they coauthor a paper. (vii) Highenergy physics citation network within the hep-th category of arXiv (HEP) [44], which isoriginally a directed network. For each network, we removed the link weight, self-loops, anddirection of the link, and submitted the LCC to the following analysis. Summary statisticsof these networks including the modularity, Q, are shown in Tables S1 and S2.
We do not investigate the Betweenness immunization algorithm due to its high computational cost (i.e., O(N M ) time for calculating the betweenness centrality of all nodes [24],hence O(N 2 M ) time for removing O(N ) nodes).
The performance of the diﬀerent immunization algorithms is compared on two empirical
networks in Fig. 3. Among the 12 empirical networks that we tested, these two networks
yielded the smallest and largest modularity values as maximized by the Louvain algorithm.
The ﬁgure indicates that the CbCI algorithm combined with Infomap or Walktrap performs
better than the previously proposed algorithms including the CI algorithm in both networks.
The CbCI algorithm performs better than the CI algorithm in many other empirical networks as well (Fig. S2(b)–(m)). Furthermore, the CbCI algorithm combined with a diﬀerent
community detection algorithm also outperforms the CI algorithm in most of the networks(Fig. S2(b)–(m)).
To be quantitative, we measure the fraction of removed nodes at which the network
fragments into suﬃciently small connected components, i.e.,qc ≡ inf{q : G(q) < θ},(8)where we remind that G(q) is the size of the LCC normalized by N . We set θ = 0.05. We
calculate qc for each combination of a network and an immunization algorithm.
The value of qc for each immunization algorithm normalized by the qc value for the CI
algorithm is plotted in Fig. 4. A symbol represents a network. A small normalized valueof qc implies a high eﬃciency of the immunization algorithm. As expected, the Degree
immunization algorithm performs worse than the CI in all the tested networks (Fig. 4(c)).
For the CbCI algorithm combined with Infomap, qc is smaller by 15.0% to 49.7% than thatfor the CI algorithm (Fig. 4(a)). The CbCI algorithm combined with Walktrap shows asimilar performance for all but one networks (Fig. 4(b)). The CbCI algorithm combined
9with three of the other four community detection algorithms performs better than the CI
algorithm for networks with relatively strong community structure (Fig. S3). The CbDI
algorithm combined with Infomap performs better than the CI algorithm for all networks,
but to a lesser extent than the CbCI algorithm combined with Infomap does (Fig. 4(d)).
The CbDI algorithm combined with Walktrap (Fig. 4(e)) and the other four community
detection algorithms (Fig. S3) performs worse than the CI algorithm. The LSP algorithm
performs worse than the CI algorithm in a majority of the networks (Fig. 4(f)).
Even if two immunization algorithms yield the same qc value on the same network, G(q)may considerably drop at a smaller q value with one immunization algorithm than theother algorithm. To quantify the performance of immunization algorithms in this sense, wemeasure the size of the LCC integrated over q values [7, 45], i.e.,

1 G≡
G(i/N ).
N i=0
N

(9)

It should be noted that G is the area under the curve when G(q) is plotted against q andranges between 0 and 1/2. A small G value implies a good performance of an immunization
algorithm.
The value of G for each immunization algorithm normalized by that for the CI algorithm is plotted in Fig. 5. The CbCI algorithm combined with Infomap outperforms the CI
algorithm in 11 out of the 12 networks in terms of G (Fig. 5(a)). Similarly, the CbCI algorithm combined with Walktrap outperforms the CI algorithm in ten out of the 12 networks(Fig. 5(b)). The CbCI combined with any of the other four community detection algorithms
outperforms the CI algorithm in roughly half of the networks and tends to be eﬃcient for
networks having large modularity values as determined by the Louvain algorithm (Fig. S4).
In particular, for the three networks with the largest modularity, the CbCI algorithm combined with any of the six community detection algorithms outperforms the CI algorithm.
The Degree, CbDI, and LSP algorithms are less eﬃcient than the CI algorithm in terms of
G (Figs. 5(c)–(f) and S4).
10

Why do Infomap and Walktrap marry better with the CbCI algorithm than theother community detection algorithms?

We have shown that the CbCI algorithm is more eﬃcient when it is combined with Infomap or Walktrap, in particular Infomap, than with the other four community detection
algorithms. To explore why, we start by measuring the clustering coeﬃcient [46] of theunweighted version of the coarse-grained networks. We do so because in theory the CI assumes locally tree-like networks [9, 47]. High clustering in the coarse-grained network may
discourage the CbCI algorithm. For each empirical network, we measure the Pearson correlation coeﬃcient between the clustering coeﬃcient and qc normalized by the value for the CI
algorithm. We use the result for each community detection algorithm as a data point suchthat the correlation coeﬃcient is calculated on the basis of six data points. The results areshown in Table I. We ﬁnd that the clustering coeﬃcient is not consistently correlated with
the normalized qc . The results are qualitatively the same with a weighted clustering coeﬃcient [48, 49] (Table I). We obtain similar results if G instead of qc is used as a performancemeasure (Table II). It should be noted that diﬀerent community detection algorithms yield
suﬃciently diﬀerent clustering coeﬃcient values including large values (Fig. S5(a)). We conclude that the lack of local tree-like structure in the coarse-grained networks is not a strong
determinant of the performance of the CbCI algorithm. This result does not contradict
those for the original CI algorithm, which assumes local tree-like networks, because the CI
algorithm is practically eﬃcient on loopy networks as well [9].
We have set  = 2, thus ignoring the contribution of nodes in coarse-grained networks
three or more hops away from a focal node. In fact, large coarse-grained networks may havea large mean path length and deteriorate the performance of the CbCI algorithm. Therefore, we calculate the correlation coeﬃcient between NC , i.e., the number of the detected
communities, and qC , and between the mean path length in the unweighted coarse-grained
network and qC (Table I). The correlation eﬃcient between G and either NC or the mean
path length is also measured (Table II). The tables indicate that the performance of a community detection algorithm is not consistently correlated with the mean path length. It iscorrelated with NC , but in the manner such that the performance of the CbCI algorithm
improves as NC increases, contrary to the aforementioned postulated mechanism. Therefore,
the use of  = 2 does not probably explain the reason why a community detection algorithm
11marries the CbCI algorithm better than another.

In fact, the CbCI algorithm performs well when the detected communities have relatively
similar sizes. To show this, we measure the entropy in the partitioning, which is deﬁned
 C



by N
c=1 (Nc /N ) log(Nc /N ), where Nc is the number of nodes in the cth community. The
entropy ranges between 0 and log NC . A large entropy value implies that the partitioningof the network is relatively egalitarian. The correlation coeﬃcient between the entropy andthe normalized qc is shown in Table I for each network. The entropy and qc are negatively
correlated with each other for all networks and strongly so for most of the networks. This
result is robust when we normalize the entropy by the largest possible value, i.e., log NC(Table I), and when the performance measure is replaced by G (Table II).

To assess the robustness of this ﬁnding, we calculate the same correlation coeﬃcient
between either the unnormalized or normalized entropy and one of the two performancemeasures, but for each community detection algorithm. Now each empirical network constitutes a data point based on which the correlation coeﬃcient is calculated. The correlationcoeﬃcient values are shown in Table III. Although the correlation is weaker than in theprevious case, the correlation between the entropy and either the normalized qC or G islargely negative, which is consistent with the results shown in Tables I and II. The correlation coeﬃcient between Q and each of the performance measure is also shown in Table III.
The entropy provides a weaker determinant of the performance as compared to Q, which is
expected because the CbCI algorithm is designed for networks with community structure.
Nevertheless, the entropy provides a larger (i.e., more negative) correlation value than Q
does in some cases (Table III).

Infomap tends to detect a large number of communities (Table S2) whose size is lessheterogeneously distributed than the case of the other community detection algorithms(Figs. S5(i) and (k)). We consider that this is a main reason why Infomap is eﬀective whencombined with the CbCI algorithm. Roughly speaking, the label-propagation algorithm
tends to yield a similarly large number of communities, NC (Table S2). However, the sizeof the community is more heterogeneously distributed with the label-propagation algorithm
than with Infomap, as quantiﬁed by the entropy measures (Figs. S5(i) and (k)).
12

DISCUSSION

We showed that the CbCI immunization algorithm outperforms the CI and some otheralgorithms when a given network has community structure. The algorithm aims to pinpoint
nodes that connect diﬀerent communities at a reasonable computational cost. The CbCI
algorithm is in particular eﬃcient when Infomap [27, 28] is used for detecting communities
beforehand. Infomap runs suﬃciently fast at least for sparse networks [21] such that theentire CbCI algorithm runs as fast as the CI algorithm at least asymptotically in termsof the network size. The Walktrap community detection algorithm [29] is the second best
among the six candidates to be combined with the CbCI algorithm in terms of the quality of
immunization. However, Walktrap is slower than Infomap. Walktrap consumes longer timethan the main part of the CbCI algorithm, i.e., sequential node removal, when the max-heap
data structure is used for implementing the CbCI algorithm. In this case, the community
detection before starting the node removal is the bottleneck of the entire CbCI algorithm,
and the CbCI algorithm is slower than the CI algorithm. To our numerical eﬀorts, werecommend Infomap to be combined with the CbCI algorithm.
We argued that Infomap works better in combination with the CbCI algorithm thanthe other community detection algorithms do mainly because Infomap yields a relatively
egalitarian distribution of the community size. However, the distribution of the community
size is usually skewed even with Infomap [50]. The CbCI algorithm may work even better if
we use a community detection algorithm that imposes that the detected communities are of
the equal or similar sizes. This problem is known as k-balanced partitioning, where k refers
to the number of communities. Although k-balanced partitioning for general k is notoriously
hard to solve, there are various approximate algorithms for this problem [51–53]. Combining
these algorithms with the CbCI algorithm may be proﬁtable.
We partitioned the network just once in the beginning of the CbCI algorithm and used
the obtained community structure throughout the node removal procedure. This property isshared by the CbDI algorithm [5] and another immunization algorithm [11]. We may be able
to improve the performance of immunization by updating the community structure during
the node removal. Our preliminary numerical simulations did not yield an improvement of
the CbCI algorithm with online updating of community structure (section S1 in the SI). We
should also bear in mind the computational cost of community detection, which would be13

repeatedly applied in the case of online updating. Nevertheless, this line of improvement
may be worth investigating.
The CI assumes locally tree-like networks [9]. Although the CI algorithm is practicallyeﬃcient in moderately loopy networks as well [9], many empirical networks are abundantin triangles and short cycles such that they are highly loopy [1]. Dense connectivity within
a community implies that there tend to be many triangles and short cycles in a networkwith community structure [54, 55]. Then, coarse graining eﬀectively coalesces many triangles and short cycles into one supernode, possibly suppressing their detrimental eﬀects.
At the same time, however, coarse-grained networks tend to have a large clustering coeﬃcient (Fig. S5(a)). We may be able to improve the performance of the CbCI algorithm bysuppressing the eﬀect of short cycles in coarse-grained networks. Recently, a method has
been proposed to improve the accuracy of estimating the percolation threshold using nonbacktracking matrices, where redundant paths are suppressed in the counting of the paths[47]. This method applied to both CI and CbCI algorithms may enhance their performancein the immunization problem.
The recently proposed collective inﬂuence propagation (CIp ) algorithm, which can beinterpreted as the CI algorithm in the limit of  → ∞, generally yields better solutions thanthe CI algorithm does [25]. Given that we have not implemented the CIp algorithm in thepresent article, we are not arguing that the CbCI algorithm is better than the CIp algorithm.
It should also be noted that we may be able to combine the CbCI algorithm with the idea of
the CIp algorithm (i.e., using the leading left and right eigenvectors of the non-backtracking
matrix) to devise a new algorithm.

METHODS
Immunization algorithms to be compared

We compare the performance of the CI and CbCI algorithms against the following immunization algorithms.
• High degree adaptive (abbreviated as Degree) [18–20]: We sequentially remove thenode having the largest degree. If multiple nodes have the largest degree, we break
the tie by selecting one of the largest-degree nodes at random. We recalculate the14degree after each node has been removed.
• Community-based dynamical importance (CbDI) [5]: This method exploits the community structure of a network, similar to the CbCI algorithm, but calculates theimportance of a community in the coarse-grained network in terms of the so-called dynamical importance [3]. The CbDI algorithm needs a community detection algorithm.
We use each of the six community detection algorithms used in the CbCI algorithm.
The CbDI algorithm runs as follows [5]. We denote by λ̃ and ũ = (ũ1 · · · ũNC )
the largest eigenvalue and the corresponding eigenvector of Ã, respectively. Owing to
the Perron-Frobenius theorem, it holds true that λ̃ > 0 and ũi ≥ 0 (1 ≤ i ≤ NC ).
The number of links between node i and to the Jth community is denoted by kiJ ≡



NC
/λ̃, where I is the community to
A
.
We
deﬁne
x
=
k
ũ
ij
iJ
J
j∈ community J
J=1,J=I
 C
which node i belongs. The CbDI of node i is deﬁned by (2ũI − x) N
J=1,J=I kiJ ũJ . We
remove the nodes in descending order of the CbDI. If there are multiple nodes thathave the same largest CbDI value, we break the tie by selecting the node that has thelargest number of intra-community links. We recalculate the CbDI values of all theremaining nodes after removing each node. Once all the communities are disconnected,
we sequentially remove the nodes in descending order of kiI . We recalculate kiI of all
the remaining nodes after removing each node.
• The Laplacian spectral partitioning (LSP) algorithm runs as follows [10]:1. For the largest connected component (LCC), calculate the Fiedler vector, i.e.,
the eigenvector associated with the smallest positive eigenvalue of the Laplacian,L ≡ DLCC − ALCC , where DLCC denotes the NLCC × NLCC diagonal matrix whose(i, i) element is equal to the degree of the ith node in the LCC, NLCC is thenumber of nodes in the LCC, and ALCC is the adjacency matrix of the LCC.
2. Partition the NLCC nodes into two non-empty groups by thresholding on thevalue of the element in the Fiedler vector. Group 1 (group 2) consists of thenodes whose corresponding element in the Fiedler vector is higher (lower) than athreshold. There are NLCC − 1 possible ways to bipartition the nodes.
15

3. Calculate
Q = min ln

2min
2
K1 + K22+ mout ln


mout
,
K1 K2

(10)

for each bipartition, where min and mout are the numbers of intra-group and intergroup links, respectively. K1 and K2 represent the sum of the nodes’ degrees ingroups 1 and 2, respectively.
4. Find the partition that maximizes Q.
5. Given the partition, remove the node that has the largest number of inter-grouplinks. Then, recalculate the number of inter-group links for each remaining node.
Repeat the node removal until the two groups are disconnected.
6. Repeat steps 1–5 until the size of the LCC becomes less than θN , where θ = 0.01.
• High betweenness centrality adaptive (abbreviated as Betweenness) [6, 16, 22, 23]:
We remove the node with the largest betweenness centrality. If multiple nodes havethe same largest betweenness centrality value, the node having the largest degree isremoved. We recalculate the betweenness of all nodes every time we remove a node.
We excluded the dynamical importance [3] because it is less successful than the CI on
various networks [9] and than the CbDI on networks with community structure [5]. We also
excluded the immunization algorithms on the basis of the PageRank, closeness centrality,and k-core, which had been shown to be outperformed by the CI algorithm [9]. This isbecause these algorithms do not particularly exploit community structure of the network
such that there is no reason for believing that they would perform competitively on networks
with community structure.

A scale-free network model with community structure

We constructed a scale-free network with built-in community structure as follows [5]. We
ﬁrst generate a coarse-grained network whose node is regarded as community, using the
Barabási-Albert (BA) model [56] having NC = 100 nodes and mean degree six. The initial
network is the clique composed of m0 = 3 nodes, and each added node has m = 3 links.
After generating a coarse-grained network, we assign 50 nodes to each community, resulting
16

in N = 50×NC = 5000 nodes in total. For each community, the intra-community network is
given by the BA model with m0 = m = 4, which yields the mean within-community degree
equal to k = 2 [(N − m0 )m + m0 (m0 − 1)/2] /N = 7.6. Additionally, if communities I
and J are adjacent in the coarse-grained network, then nodes i ∈ I and j ∈ J are connectedwith probability kg /(6N/NC ). This guarantees that a node is adjacent to kg nodes in
diﬀerent communities on average. We set kg = 1. The mean degree of the entire network
is equal to k = 8.58 ≈ k + kg .

[1] Newman, M. E. J. Networks — An Introduction. Oxford University Press, Oxford (2010).
[2] Altarelli, F., Braunstein, A., Dall’Asta, L., Wakeling, J. R., and Zecchina, R. Containing
epidemic outbreaks by message-passing techniques. Phys. Rev. X 4, 021024 (2014).
[3] Restrepo, J. G., Ott, E., and Hunt, B. R. Weighted percolation on directed networks. Phys.
Rev. Lett. 100, 058701 (2008).
[4] Chen, Y., Paul, G., Havlin, S., Liljeros, F., and Stanley, H. E. Finding a better immunization
strategy. Phys. Rev. Lett. 101, 058701 (2008).
[5] Masuda, N. Immunization of networks with community structure. New J. Phys. 11, 123018(2009).
[6] Salathé, M. and Jones, J. H. Dynamics and control of diseases in networks with community
structure. PLOS Comput. Biol. 6, e1000736 (2010).
[7] Schneider, C. M., Mihaljev, T., Havlin, S., and Herrmann, H. J. Suppressing epidemics witha limited amount of immunization units. Phys. Rev. E 84, 061911 (2011).
[8] Zhao, D. et al. Immunization of epidemics in multiplex networks. PLOS ONE 9, e112018(2014).
[9] Morone, F. and Makse, H. A. Inﬂuence maximization in complex networks through optimal
percolation. Nature 524, 65–68 (2015).
[10] Zahedi, R. and Khansari, M. A new immunization algorithm based on spectral properties forcomplex networks. In The 7th Conference on Information and Knowledge Technology (IKT),
1–5 (2015).
[11] Requião da Cunha, B., González-Avella, J. C., and Gonçalves, S. Fast fragmentation of
networks using module-based attacks. PLOS ONE 10, e0142824 (2015).

17

[12] Mugisha, S. and Zhou, H.-J. Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94, 012305 (2016).
[13] Cohen, R., Havlin, S., and ben-Avraham, D. Eﬃcient immunization strategies for computer
networks and populations. Phys. Rev. Lett. 91, 247901 (2003).
[14] Gallos, L. K., Liljeros, F., Argyrakis, P., Bunde, A., and Havlin, S. Improving immunization
strategies. Phys. Rev. E 75, 045104(R) (2007).
[15] Gong, K. at al. An eﬃcient immunization strategy for community networks. PLOS ONE 8,
e83489 (2013).
[16] Hébert-Dufresne, L., Allard, A., Young, J.-G., and Dubé, L. J. Global eﬃciency of local
immunization on complex networks. Sci. Rep. 3, 2171 (2013).
[17] Liu, Y., Deng, Y., and Wei, B. Local immunization strategy based on the scores of nodes.
Chaos 26, 013106 (2016).
[18] Albert, R., Jeong, H., and Barabási, A.-L. Error and attack tolerance of complex networks.
Nature 406, 378–382 (2000).
[19] Callaway, D. S., Newman, M. E. J., Strogatz, S. H., and Watts, D. J. Network robustness
and fragility: Percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000).
[20] Cohen, R., Erez, K., ben-Avraham, D., and Havlin, S. Breakdown of the internet underintentional attack. Phys. Rev. Lett. 86, 3682–3685 (2001).
[21] Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174 (2010).
[22] Holme, P., Kim, B. J., Yoon, C. N., and Han, S. K. Attack vulnerability of complex networks.
Phys Rev. E 65, 056109 (2002).
[23] Ueno, T. and Masuda, N. Controlling nosocomial infection based on structure of hospitalsocial networks. J. Theor. Biol. 254, 655–666 (2008).
[24] Brandes, U. A faster algorithm for betweenness centrality. J. Math. Sociol. 25, 163–177(2001).
[25] Morone, F., Min, B., Bo, L., Mari, R., and Makse, H. A. Collective inﬂuence algorithm toﬁnd inﬂuencers via optimal percolation in massively large social media. Sci. Rep. 6, 30062(2016).
[26] Karrer, B., Newman, M. E. J., and Zdeborová, L. Percolation on sparse networks. Phys. Rev.
Lett. 113, 208702 (2014).

18

[27] Rosvall, M. and Bergstrom, C. T. Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA 105, 1118–1123 (2008).
[28] Rosvall, M., Axelsson, D., and Bergstrom, C. T. The map equation. Eur. Phys. J. Spec. Top.
178, 13–23 (2010).
[29] Pons, P. and Latapy, M. Computing communities in large networks using random walks.
In Computer and Information Sciences-ISCIS 2005, Yolum, P., Güngör, T., Gürgen, F., andÖzturan, C., editors, volume 3733 of Lecture Notes in Computer Science, 284–293. Springer
Berlin Heidelberg (2005).
[30] Raghavan, U. N., Albert, R., and Kumara, S. Near linear time algorithm to detect community
structures in large-scale networks. Phys. Rev. E 76, 036106 (2007).
[31] Clauset, A., Newman, M. E. J., and Moore, C. Finding community structure in very large
networks. Phys. Rev. E 70, 066111 (2004).
[32] Sales-Pardo, M., Guimerá, R., Moreira, A. A., and Amaral, L. A. N. Extracting the hierarchical organization of complex systems. Proc. Natl. Acad. Sci. USA 104, 15224–15229(2007).
[33] Lancichinetti, A. and Fortunato, S. Community detection algorithms: A comparative analysis.
Phys. Rev. E 80, 056117 (2009).
[34] Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. 2008, P10008 (2008).
[35] Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densiﬁcation laws, shrinking
diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 177–187. ACM, (2005).
[36] Jure, L., and Andrej, K. Stanford Network Analysis Project. http://snap.stanford.edu/.
(Date of access: 19/01/2016).
[37] University of Oregon Route Views Project. http://www.routeviews.org. (Date of access:19/01/2016).
[38] Boguñá, M., Pastor-Satorras, R., Dı́az-Guilera, A., and Arenas, A. Models of social networks
based on social distance attachment. Phys. Rev. E 70, 056122 (2004).
[39] Albert, R., Jeong, H., and Barabási, A.-L. Internet: Diameter of the world-wide web. Nature
401, 130–131 (1999).

19

[40] Ebel, H., Mielsch, L. I., and Bornholdt, S. Scale-free topology of e-mail networks. Phys. Rev.
E 66, 035103(R) (2002).
[41] Klimt, B. and Yang, Y. The enron corpus: A new dataset for email classiﬁcation research. In
Machine Learning: ECML 2004, 217–226. Springer (2004).
[42] Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure in large
networks: Natural cluster sizes and the absence of large well-deﬁned clusters. Internet Math.
6, 29–123 (2009).
[43] Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Densiﬁcation and shrinking
diameters. ACM Trans. Knowl. Discov. Data 1, 2 (2007).
[44] Batagelj, V., and Mrvar, A. Pajeck datasets (2006), http://vlado.fmf.uni-lj.si/pub/
networks/data/. (Data of access: 19/01/2016).
[45] Schneider, C. M., Moreira, A. A., Andrade, J. S., Havlin, S., and Herrmann, H. J. Mitigationof malicious attacks on networks. Proc. Natl. Acad. Sci. USA 108, 3838–3841 (2011).
[46] Watts, D. J. and Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393,
440–442 (1998).
[47] Radicchi, F. and Castellano, C. Beyond the locally treelike approximation for percolation onreal networks. Phys. Rev. E 93, 030302(R) (2016).
[48] Onnela, J.-P., Saramäki, J., Kertész, J., and Kaski, K. Intensity and coherence of motifs inweighted complex networks. Phys. Rev. E 71, 065103 (2005).
[49] Saramäki, J., Kivelä, M., Onnela, J.-P., Kaski, K., and Kertész, J. Generalizations of theclustering coeﬃcient to weighted complex networks. Phys. Rev. E 75, 027105 (2007).
[50] Lancichinetti, A., Kivelä, M., Saramäki, J., and Fortunato, S. Characterizing the community
structure of complex networks. PLOS ONE 5, e11976 (2010).
[51] Andreev, K. and Racke, H. Balanced graph partitioning. Theor. Comp. Sys. 39, 929–939(2006).
[52] Krauthgamer, R., Naor, J. S., and Schwartz, R. Partitioning graphs into balanced components. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘09, 942–949 (2009).
[53] Feldmann, A. E. and Foschini, L. Balanced partitions of trees and applications. Algorithmica
71, 354–376 (2015).

20

[54] Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. Deﬁning and identifying
communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658–2663 (2004).
[55] Palla, G., Derényi, I., Farkas, I., and Vicsek, T. Uncovering the overlapping community
structure of complex networks in nature and society. Nature 435, 814–818 (2005).
[56] Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. Science 286,
509–512 (1999).

ACKNOWLEDGEMENTS

N.M. acknowledges the support provided through JST, CREST, and JST, ERATO,
Kawarabayashi Large Graph Project. T.K. acknowledges ﬁnancial support from the Japan
Society for the Promotion of Science KAKENHI Grants no. 25780203, 15H01948, and
16K03551. We thank Flaviano Morone and Taro Takaguchi for providing codes for the
CI algorithm.

AUTHOR CONTRIBUTIONS

T.K. and N.M. conceived the research. T.K. conducted the analysis. T.K. and N.M.
discussed the results and wrote the manuscript.

COMPETING FINANCIAL INTERESTS STATEMENT

The authors declare no competing ﬁnancial interests.

21

(a)

(b)
‫ܫ‬
‫ܫ‬

‫ ܫ‬ା (= ‫) ିܬ‬෨߲Ball(‫ܫ‬,1)‫ܬ‬‫ݖ‬ூᇱ = 10෨߲Ball(‫ܫ‬,2)

node ݅‫ ܫ‬ା (= ‫) ିܬ‬‫ܣ‬௜௜ శ = 1‫ܣ‬ሚ ூூ శ = 4‫ܬ‬‫ݖ‬௃ᇱᇱ = 3(c)node inode jFIG. 1. Concept of the community-based collective inﬂuence. (a) Egocentric view of the coarsegrained network. Each circle represents a community. Two communities are adjacent by a weighted
link if a node in one community is connected to at least one node in the other community. The
link weight in the coarse-grained network is equal to the number of links that connect the two
communities in the original network. Local tree-like structure of the coarse-grained network is
assumed. (b) Illustration of zI and zJ for  = 2, in which case I + = J − . A line represents
a link in the original network. The dashed circle represents the Ith community. (c) Schematicof community-based reinsertion. A dashed circle represents a community. Suppose that we will
reinsert either node i or j. If reinserted, node i and j would have a path to two and threecommunities, respectively. Therefore, we reinsert node i.

22



&,
&E&,
'HJUHH&E',/63%HWZHHQQHVV



E 


G(q)

G(q)

D










q







&,
&E&,,QIRPDS&E&,:DONWUDS'HJUHH&E',,QIRPDS&E',:DONWUDS/63%HWZHHQQHVV





q





FIG. 2. Normalized size of the LCC, G(q), plotted against the fraction of removed nodes, q, inmodel networks with N = 5000. A curve corresponds to an immunization algorithm. See Methods
for the abbreviations. (a) Scale-free network with prescribed community structure. (b) BA model.

23



G(q)





&,
&E&,,QIRPDS&E&,:DONWUDS'HJUHH&E',,QIRPDS&E',:DONWUDS
/63





q



E 
G(q)

D











q



FIG. 3. Normalized size of the LCC, G(q), plotted against the fraction of removed nodes, q, in two
empirical networks. (a) E-mail communication network in Enron. (b) World Wide Web.

24

normalized qc

D &E&,,QIRPDS

E &E&,:DONWUDS

F

































G &E',,QIRPDS

H &E',:DONWUDS

I































'HJUHH





/63





$6
$6
3*3
:::
HPDLOXQL
HPDLO(QURQ&$*U4F&$$VWURSK&$&RQGPDW&$+HS3K&$+HS7K+(3VFDOHIUHHZLWK
FRPPXQLWLHVQ
FIG. 4. The fraction of removed nodes to fragment the network, qc , for an immunization algorithm
divided by the value for the CI algorithm. (a) CbCI combined with Infomap. (b) CbCI combinedwith Walktrap. (c) High degree adaptive (Degree). (d) CbDI combined with Infomap. (e) CbDI
combined with Walktrap. (f) Laplacian spectral partitioning (LSP). A symbol represents a network.
The cross represents the model network used in Fig. 2(a). The modularity value, Q, is determinedby the Louvain algorithm.

25

normalized G

D &E&,,QIRPDS

E &E&,:DONWUDS

F

































G &E',,QIRPDS

H &E',:DONWUDS

I






















'HJUHH





/63












$6
$6
3*3
:::
HPDLOXQL
HPDLO(QURQ&$*U4F&$$VWURSK&$&RQGPDW&$+HS3K&$+HS7K+(3VFDOHIUHHZLWK
FRPPXQLWLHVQ
FIG. 5. The G value normalized by that for the CI algorithm. (a) CbCI combined with Infomap.
(b) CbCI combined with Walktrap. (c) Degree. (d) CbDI combined with Infomap. (e) CbDI
combined with Walktrap. (f) LSP. The Q value is determined by the Louvain algorithm.

26

TABLE I. Correlation coeﬃcient between an explanatory variable and the normalized qc . The
clustering coeﬃcient is deﬁned by the number of triangles containing the ith node divided byki (ki − 1)/2, which is averaged over all nodes 1 ≤ i ≤ N . The weighted clustering coeﬃcient is
1/3 /[k (k − 1)], which is averaged over i [48, 49]. Here, ŵ =deﬁned by Ni iijj,k=1;j,k=i (ŵij ŵjk ŵki )wij / max1≤i ,j  ≤N (wi j  ), and wij is the weight of the link between the ith and jth nodes. We
calculated the correlation coeﬃcient for each network on the basis of the data points obtained
from the six community detection algorithms. The scattergrams based on which the correlationcoeﬃcient has been calculated are shown in Figs. S5(a), (c), (e), (g), (i), and (k).
clustering
coeﬃcientweightedclustering
coeﬃcient

AS-1

0.238

0.120

−0.415−0.354−0.523−0.608AS-2−0.2580.119−0.4170.065−0.319−0.203

PGP

0.298

0.490

−0.603−0.534−0.667−0.781WWW−0.005−0.4300.306−0.3750.216−0.169email-uni

0.213−0.053−0.3620.125−0.446−0.568email-Enron−0.278−0.398−0.073−0.136−0.650−0.817

CA-GrQc

0.438

0.345

−0.773−0.458−0.891−0.934

CA-Astroph−0.154−0.005−0.406−0.144−0.764−0.826

CA-Condmat

0.121−0.181−0.6530.219−0.820−0.918CA-HepPh

0.729

0.792

−0.845−0.569−0.932−0.781CA-HepTh−0.200−0.118

0.178

0.325

−0.067−0.320

0.314

0.204

−0.718−0.042−0.842−0.759

HEP

NC

27

mean path
lengthentropy normalized
entropyTABLE II. Correlation coeﬃcient between an explanatory variable and the normalized G for each
network. We calculate the correlation coeﬃcient for each network on the basis of the data points
obtained from the six community detection algorithms. The scattergrams based on which thecorrelation coeﬃcient has been calculated are shown in Figs. S5(b), (d), (f), (h), (j), and (l).
clustering
coeﬃcientweightedclustering
coeﬃcient

AS-1

0.064

0.284

−0.813−0.259−0.813−0.604AS-2−0.3690.416−0.6930.105−0.660−0.449

PGP

0.084

0.295

−0.489−0.586−0.603−0.766WWW−0.3670.111−0.7130.281−0.820−0.694

email-uni

0.394

0.362

−0.8100.043−0.823−0.595

email-Enron−0.381−0.224−0.474−0.258−0.804−0.798

CA-GrQc

0.034

0.045

−0.467−0.043−0.679−0.909CA-Astroph−0.313−0.112−0.137−0.232−0.526−0.700CA-Condmat

0.334−0.024−0.7060.387−0.851−0.839CA-HepPh

0.227

0.419

−0.424−0.214−0.607−0.685

CA-HepTh

0.248

0.629

−0.632−0.129−0.754−0.730−0.0670.400−0.6360.395−0.759−0.722

HEP

NC

28

mean path
lengthentropy normalized
entropyTABLE III. Correlation coeﬃcient between an explanatory variable and a performance measure foreach community detection algorithm. We calculate the correlation coeﬃcient for each community
detection algorithm on the basis of the data points obtained from the 12 empirical networks. qc
and G indicate the values normalized by those for the CI algorithm. The scattergrams based on
which the correlation coeﬃcient has been calculated are shown in Fig. S6.
entropy[] [] [] [] [] [] [] [] []Qnormalized entropy

qc

G

qc

G

qc

G

Infomap−0.0880.358−0.017−0.206−0.576−0.210

Walktrap−0.5060.014−0.434−0.201−0.348−0.128label propagation−0.690−0.659−0.630−0.687−0.689−0.797

fast greedy−0.211−0.0990.067−0.081−0.015−0.310simulated annealing−0.6950.057−0.288−0.005−0.330−0.391

Louvain−0.791−0.001−0.267−0.370−0.707−0.370Supplementary Information:
Fragmenting networks by targeting collective inﬂuencers at amesoscopic level
Teruyoshi Kobayashi and Naoki Masuda

S1.

CBCI ALGORITHM UNDER AN ONLINE UPDATING OF COMMUNITYSTRUCTURE

As described in the main text, the CbCI algorithm carries out community detection only
once at the beginning of the node removal process. This saves computation time but may
worsen the performance of the immunization because the organization of communities maychange as we remove nodes. In this section, we investigate the impact of recalculating
the community structure repeatedly during the node removal process. We recalculate thepartitioning of the network every time we remove 10−3 N nodes. By feeding the most upto-date partitioning to the CbCI algorithm, we determine the tentative order of the node
removal. Then, we reinsert the nodes in the same manner as the original CbCI algorithm
does. The entire reinsertion procedure uses the community structure of the original network,i.e., that determined before the node removal. We reinsert the nodes one by one. We focus
on Infomap and Walktrap, with which the CbCI algorithm performs the best. We use AS-1,
PGP, and CA-GrQc networks for illustration.
The immunization results for the CbCI algorithm with online updating of the community
structure are compared with those for the original CbCI algorithm and the CI algorithm in
Fig. S1. The ﬁgure indicates that online updating of the community structure improves theperformance of the CbCI algorithm in some cases but not in others.

1D$6,QIRPDS&E&,&E&,RQOLQH
&,

G(q)




G





&E&,
&E&,RQOLQH
&,










3*3,QIRPDS








$6:DONWUDS



E

H



&$*U4F,QIRPDS







  3*3:DONWUDS






F

I











&$*U4F:DONWUDS  

q











FIG. S1. Online updating of the community structure in the CbCI algorithm. In each panel, thesize of the LCC under the original CbCI algorithm, the CbCI algorithm with online updating of
the community structure, and the CI algorithm is plotted against q.

2

(a) 0.8

BA modelCI
CbCI, Infomap
CbCI, Walktrap
CbCI, LP
CbCI, fast greedy
CbCI, SACbCI, Louvain
DegreeCbDI, Infomap
CbDI, Walktrap
CbDI, LP
CbDI, fast greedy
CbDI, SA
CbDI, Louvain
LSP
Betweenness

G(q)

0.6

0.4

0.2

0
0.2

0.3

0.4

0.5

q

(b) 1

0.6

AS-1

G(q)

0.8
0.6
0.4
0.2
0

0

0.01

0.02

0.03

q

0.04

0.05

0.06

FIG. S2. Normalized size of the LCC, G(q), plotted against the fraction of removed nodes, q,
for diﬀerent networks and immunization algorithms. In (a), the results for the label-propagation
community detection algorithm are absent because it yields no community (i.e., Nc = 0) for thisnetwork.

3

(c) 1

AS-2

G(q)

0.8
0.6
0.4
0.2
0

0

0.01

0.02

(d) 1

0.03

q

0.04

0.05

0.06

PGP

G(q)

0.8
0.6
0.4
0.2
0

0

0.02

0.04

q

4

0.06

0.08

(e) 1

WWW

G(q)

0.8
0.6
0.4
0.2
0

(f)

0

0.01

0.02

q

0.03

0.04

email-uni

1

G(q)

0.8
0.6
0.4
0.2
0

0

0.01

q

5

0.02

0.03

(g) 1email-Enron

G(q)

0.8
0.6
0.4
0.2
0

0

0.05

(h) 1

q

0.1

0.15

CA-GrQc

G(q)

0.8
0.6
0.4
0.2
0

0

0.05

0.1

q

6

0.15

0.2

(i)

CA-Astroph

1

G(q)

0.8
0.6
0.4
0.2
0

(j)

0

0.1

0.2

0.3

q

0.4

CA-Condmat

1

G(q)

0.8
0.6
0.4
0.2
0

0

0.05

0.1

q

7

0.15

0.2

0.25

(k) 1CA-HepPh

G(q)

0.8
0.6
0.4
0.2
0

(l)

0

0.05

0.1

0.15

q

0.2

0.25

0.3

CA-HepTh

1

G(q)

0.8
0.6
0.4
0.2
0

0

0.05

0.1

8

q

0.15

0.2

(m) 1

HEP

G(q)

0.8
0.6
0.4
0.2
0

0

0.1

0.2

q

9

0.3

0.4

0.5

&E&,,QIRPDS
























&E&,IDVWJUHHG\

normalized qc&E&,/3&E&,:DONWUDS





























&E',,QIRPDS













&E',:DONWUDS







&E',IDVWJUHHG\

















&E',/RXYDLQ&E',6$









&E',/3

























&E&,/RXYDLQ&E&,6$


















$6
$6
3*3
:::
HPDLOXQL
HPDLO(QURQ&$*U4F&$$VWURSK&$&RQGPDW&$+HS3K&$+HS7K+(3VFDOHIUHHZLWK
FRPPXQLWLHVQ
FIG. S3. Threshold fraction of removed nodes to fragment the network, qc , for the CbCI andCbDI algorithms combined with diﬀerent community detection algorithms. The shown qc values
are normalized by those for the CI algorithm. Each panel represents an immunization algorithm. A
symbol represents a network. We calculated the modularity (i.e., Q) using the Louvain algorithm.
The results for Infomap and Walktrap are identical to those shown in Figs. 4(a), (b), (d), and (e).

10&E&,,QIRPDS



















&E&,IDVWJUHHG\










&E&,6$



























&E',,QIRPDS







&E',:DONWUDS















&E',IDVWJUHHG\



&E',6$




































&E',/3









&E&,/RXYDLQ













&E&,/3






normalized G&E&,:DONWUDS&E',/RXYDLQ












$6
$6
3*3
:::
HPDLOXQL
HPDLO(QURQ&$*U4F&$$VWURSK&$&RQGPDW&$+HS3K&$+HS7K+(3VFDOHIUHHZLWK
FRPPXQLWLHVQ
FIG. S4. The normalized size of the LCC averaged over q, i.e., G, for the CbCI and CbDI
algorithms. The shown values are normalized by those for the CI algorithm. See the caption ofFig. S3 for the legends. The results for Infomap and Walktrap are identical to those shown in
Figs. 5(a), (b), (d), and (e).

11

D

$6

$6
ρ = 0.238









ρ = −0.258









normalized qc

ρ = −0.005






































ρ = 0.121













+(3

ρ = −0.200








&$&RQGPDW&$+HS7K

ρ = 0.729







ρ = −0.278






ρ = −0.154&$+HS3K










HPDLO(QURQ&$$VWURSKρ = 0.438

ρ = 0.213&$*U4F







ρ = 0.298






HPDLOXQL

:::





3*3

ρ = 0.314












,QIRPDS:DONWUDS/3
IDVWJUHHG\
6$/RXYDLQ

FOXVWHULQJFRHIILFLHQW
FIG. S5. Comparison of the community detection algorithms on the basis of the relationships
between structural measures of the coarse-grained network and performance measures. The structural measure is calculated for each partitioning of the network. Plotted are the relationships
between (a) the unweighted clustering coeﬃcient and qc , (b) the unweighted clustering coeﬃcientand G, (c) the weighted clustering coeﬃcient and qc , (d) the weighted clustering coeﬃcient andG, (e) Nc and qc , (f) Nc and G, (g) the mean path length and qc , (h) the mean path length andG, (i) the unnormalized entropy and qc , (j) the unnormalized entropy and G, (k) the normalized
entropy and qc , and (l) the normalized entropy and G. The qc and G values are those for the CbCI
algorithm normalized by the values for the CI algorithm.

12

E






$6

$6

3*3

ρ = 0.064

ρ = −0.369 




ρ = 0.084











normalized G

:::





























ρ = 0.334







ρ = −0.067









FOXVWHULQJFRHIILFLHQW

13



+(3

ρ = 0.248








&$&RQGPDW&$+HS7K

ρ = 0.227







ρ = −0.381

ρ = −0.313 









&$+HS3K









HPDLO(QURQ&$$VWURSKρ = 0.034








ρ = 0.394 &$*U4F







HPDLOXQL

ρ = −0.367 















F

$6
ρ = 0.120







normalized qc

$6



ρ = 0.119










:::










































ρ = −0.181











+(3
ρ = 0.204







ZHLJKWHGFOXVWHULQJFRHIILFLHQW

14



&$&RQGPDWρ = −0.118








ρ = −0.398






&$+HS7K

ρ = 0.792







HPDLO(QURQρ = −0.005&$+HS3K







&$$VWURSKρ = 0.345ρ = −0.053&$*U4F








ρ = 0.490






HPDLOXQL

ρ = −0.430






3*3





G





normalized G



$6

$6

3*3

ρ = 0.284

ρ = 0.416

ρ = 0.295












:::



























&$+HS7K

ρ = 0.419

ρ = 0.629

















ρ = −0.024







+(3
ρ = 0.400









ZHLJKWHGFOXVWHULQJFRHIILFLHQW

15



&$&RQGPDW&$+HS3K

ρ = −0.112 











ρ = −0.224






&$$VWURSKρ = 0.045



HPDLO(QURQρ = 0.362






&$*U4F








HPDLOXQL

ρ = 0.111















H






normalized qc



$6

$6

3*3

ρ = −0.415

ρ = −0.417

ρ = −0.603












ρ = 0.306

ρ = −0.362






 ρ = −0.773









ρ = −0.845











ρ = −0.653







&$+HS7K










Nc

16

 

&$&RQGPDWρ = 0.178

ρ = −0.073








ρ = −0.406






&$+HS3K









HPDLO(QURQ&$$VWURSK&$*U4F










HPDLOXQL

:::

















+(3
ρ = −0.718











I






normalized G



$6

$6

3*3

ρ = −0.813

ρ = −0.693

ρ = −0.489












ρ = −0.713








 









ρ = −0.424









ρ = −0.706









ρ = −0.632











Nc

17

 

&$&RQGPDW&$+HS7K&$+HS3K









ρ = −0.137








ρ = −0.474






&$$VWURSKρ = −0.467







HPDLO(QURQρ = −0.810&$*U4F










HPDLOXQL

:::

















+(3
ρ = −0.636











J

$6

$6





ρ = −0.354










normalized qc

















ρ = −0.569




















ρ = 0.219







+(3

ρ = 0.325







PHDQSDWKOHQJWK

18&$&RQGPDWρ = −0.144ρ = −0.136&$+HS7K&$+HS3K





ρ = 0.125



HPDLO(QURQ&$$VWURSKρ = −0.458

ρ = −0.534







&$*U4F










HPDLOXQL

ρ = −0.375

ρ = 0.065



:::





3*3

ρ = −0.042





K





$6

$6

ρ = −0.259 




ρ = 0.105



normalized G

ρ = 0.281









ρ = 0.043








ρ = −0.258

ρ = −0.232 




ρ = 0.387









&$+HS7K
ρ = −0.129 




ρ = 0.395









PHDQSDWKOHQJWK

19



+(3

ρ = −0.214 







&$&RQGPDWρ = −0.043 







HPDLO(QURQ&$$VWURSK&$+HS3K





ρ = −0.586







&$*U4F










HPDLOXQL

:::





3*3



L






$6

$6

3*3

ρ = −0.523

ρ = −0.319

ρ = −0.667












normalized qc

ρ = 0.216ρ = −0.446










ρ = −0.891

























HQWURS\20ρ = −0.820









ρ = −0.067

&$&RQGPDW&$+HS7K&$+HS3K









ρ = −0.650








ρ = −0.764








ρ = −0.932



HPDLO(QURQ&$$VWURSK&$*U4F









HPDLOXQL

:::
















+(3
ρ = −0.842











M






$6

$6

3*3

ρ = −0.813 




ρ = −0.660 




ρ = −0.603







normalized G

:::







ρ = −0.823
&$*U4F

























HQWURS\

21&$&RQGPDWρ = −0.851







+(3

ρ = −0.754 







ρ = −0.804






&$+HS7K

ρ = −0.607 









HPDLO(QURQρ = −0.526 




&$+HS3K







&$$VWURSKρ = −0.679 











HPDLOXQL

ρ = −0.820 











ρ = −0.759







N

$6





ρ = −0.608



$6









normalized qc

:::


















&$+HS3K





ρ = −0.781



















ρ = −0.918





+(3

ρ = −0.320








QRUPDOL]HGHQWURS\

22

&$&RQGPDWρ = −0.826

ρ = −0.817

&$+HS7K







HPDLO(QURQρ = −0.568

ρ = −0.781

&$$VWURSKρ = −0.934







&$*U4F










HPDLOXQL

ρ = −0.169



3*3

ρ = −0.203

ρ = −0.759





O

$6

$6






ρ = −0.449 




ρ = −0.766









normalized G

HPDLO(QURQ




ρ = −0.595 ρ = −0.798











&$$VWURSK&$&RQGPDWρ = −0.909 




ρ = −0.700 




ρ = −0.839











&$+HS7K&$+HS3K







ρ = −0.694 




&$*U4F







HPDLOXQL

:::





3*3

ρ = −0.604 






+(3

ρ = −0.685 




ρ = −0.730 




ρ = −0.722











QRUPDOL]HGHQWURS\

23

normalized qc

D,QIRPDS
















E











$6
$6
3*3
:::
HPDLOXQL
HPDLO(QURQ&$*U4F&$$VWURSK&$&RQGPDW&$+HS3K&$+HS7K+(3



/RXYDLQρ = −0.791










HQWURS\:DONWUDS/3

ρ = −0.017

ρ = −0.434

ρ = −0.630














IDVWJUHHG\








ρ = −0.695






,QIRPDS








ρ = −0.690






6$

ρ = −0.211






/3

ρ = −0.506

IDVWJUHHG\



normalized qc:DONWUDS

ρ = −0.088

ρ = 0.067










6$









/RXYDLQ

ρ = −0.288

ρ = −0.267












QRUPDOL]HGHQWURS\FIG. S6. Comparison of the diﬀerent networks using the relationship between the entropy andperformance measures. (a) Relationship between the unnormalized entropy and the normalized qc .
(b) Relationship between the normalized entropy and the normalized qc . (c) Relationship between
the unnormalized entropy and the normalized G. (d) Relationship between the normalized entropy
and the normalized G.

24normalized GF,QIRPDS









IDVWJUHHG\





G






















HQWURS\:DONWUDS

IDVWJUHHG\



















/RXYDLQ







QRUPDOL]HGHQWURS\25

ρ = −0.687






ρ = −0.005





/3

6$

ρ = −0.081







ρ = −0.001











/RXYDLQρ = 0.057 ρ = −0.206  ρ = −0.201






ρ = −0.659






6$

,QIRPDS








ρ = −0.099 /3 ρ = 0.014




ρ = 0.358








normalized G:DONWUDS

ρ = −0.370







TABLE S1. Summary statistics of the model and empirical networks. N , M , and k represent
the number of nodes, that of links, and the average degree, respectively.
NetworkNM

k

References

scale-free with
communities

5,000

21,440

8.58

[1]

BA

5,000

29,979

11.99

[2]

AS-1

6,474

12,572

3.88[3, 4]

AS-2

10,67022,002

4.12[3, 4]

PGP

10,68024,316

4.55

[5]

WWW

99,193

178,840

3.61[6]

email-uni

63,49596,7773.05[7]email-Enron

33,696

180,811 10.73 [4, 8–10]

CA-GrQc

4,158

13,422

6.46[4, 11]CA-Astroph

17,903

196,972 22.00[4, 11]

CA-Condmat

21,36391,286[4, 11]CA-HepPh

11,204

117,619 21.00 [3, 4, 12]

CA-HepTh

8,638

24,806

HEP

27,400352,021 25.69

26

8.55

5.74

[3, 4, 12][13]

TABLE S2. Community structure of the model and empirical networks detected by diﬀerent algorithms. The number of communities, NC , and the modularity, Q, are shown for each community
detection algorithm. LP: label propagation. SA: simulated annealing. We implemented the Infomap, label propagation, and simulated annealing algorithm using the codes available at [14], theWalktrap using the codes available at [15], the fast greedy algorithm using the codes available at[16], and the Louvain algorithm using the codes available at [17].
Infomap

Walktrap

Network

NC

Q

NC

Q

NC

Q

NC

Q

NC

Q

NC

Q

BA

256

0.174

219

0.166

0

n.a.

12

0.250

19

0.250

13

0.253

AS-1

358

0.551

184

0.599

172

0.552

38

0.603

33

0.590

30

0.626

AS-2

524

0.544

262

0.599

241

0.549

42

0.614

33

0.579

33

0.629

PGP

924

0.813

946

0.830

959

0.817

205

0.853

118

0.812

96

0.883

WWW

3,643 0.823 3,607 0.805 4,334 0.815 1,067 0.850

936

0.822

186

0.890

email-uni

2,534 0.705 1,731 0.716 2,183 0.689

310

0.728

389

0.718

121

0.777

email-Enron

1,385 0.544 1,056 0.544

958

0.324

525

0.511

235

0.585

191

0.608

CA-GrQc

323

0.785

0.799

358

0.780

70

0.796

63

0.792

43

0.848

CA-Astroph

735

0.561 1,154 0.542

344

0.292

183

0.492

55

0.586

42

0.627

CA-Condmat 1,186 0.646 1,302 0.627 1,475 0.634

266

0.628

189

0.600

53

0.726

CA-HepPh

627

0.612

910

0.596

373

0.451

138

0.583

74

0.628

39

0.658

CA-HepTh

596

0.680

549

0.676

640

0.666

115

0.703

101

0.661

53

0.755

HEP

674

0.579

773

0.608

477

0.613

120

0.525

33

0.606

29

0.653

290

LP

27

fast greedy

SA

Louvain[1] Masuda, N. Immunization of networks with community structure. New J. Phys. 11(12),123018 (2009).
[2] Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. Science 286(5439),
509–512 (1999).
[3] Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densiﬁcation laws, shrinking
diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 177–187. ACM, (2005).
[4] http://snap.stanford.edu/.
[5] Boguñá, M., Pastor-Satorras, R., Dı́az-Guilera, A., and Arenas, A. Models of social networks
based on social distance attachment. Phys. Rev. E 70, 056122, Nov (2004).
[6] Albert, R., Jeong, H., and Barabási, A.-L. Internet: Diameter of the world-wide web. Nature
401(6749), 130–131 (1999).
[7] Ebel, H., Mielsch, L. I., and Bornholdt, S. Scale-free topology of e-mail networks. Phys. Rev.
E 66, 035103(R) (2002).
[8] Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure in large
networks: Natural cluster sizes and the absence of large well-deﬁned clusters. Internet Math.
6(1), 29–123 (2009).
[9] Klimt, B. and Yang, Y. The enron corpus: A new dataset for email classiﬁcation research. In
Machine Learning: ECML 2004, 217–226. Springer (2004).
[10] https://www.cs.cmu.edu/~./enron/.
[11] Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Densiﬁcation and shrinking
diameters. ACM Trans. Knowl. Discov. Data 1(1), 2 (2007).
[12] Gehrke, J., Ginsparg, P., and Kleinberg, J. Overview of the 2003 kdd cup. ACM SIGKDD
Explorations Newsletter 5(2), 149–151 (2003).
[13] http://vlado.fmf.uni-lj.si/pub/networks/data/.
[14] https://sites.google.com/site/andrealancichinetti/software.
[15] https://www-complexnetworks.lip6.fr/~latapy/PP/walktrap.html.
[16] http://igraph.org/python/.
[17] https://sites.google.com/site/findcommunities/.

28