link connects different communities
in the figure. Two diffusion processes
are triggered by the maximum degree
nodes, as in Figure 1a, and minimum
degree nodes, as in Figure 1b, respectively. Theoretically, the requirement
of simultaneous diffusion of source
nodes is not necessary due to the independent infection process between
each infected node and its susceptible
neighbors. However, to ensure a clear,
quick observation of a diffusion phenomenon, as in, say, letting source
nodes (represented by two red nodes
in Figure 1) initiate a diffusion process
simultaneously. Based on the propagation rules defined in a typical “
two-state” diffusion model,
22 each infected
node tries to infect all its susceptible
neighbors with a certain probability at
each time step, bringing uncertainty
during the propagation process. For
example, as shown in Figure 1a, “A”
is infected by “E” at t = 3, rather than
by its source node neighbor at t = 1 or
t = 2. Meanwhile, at t = 8, “D” remains
susceptible until infected by “C” at t =
10. In Figure 1a, information diffuses
quickly at the initial stage. The speed
of diffusion could be enhanced by increasing the initial number of source
nodes. Note also two factors concerning the effect of network structure on
the potential diffusion process:
Effective diffusion links. The effective
diffusion links represent the connec-
tions that make a key contribution to
the diffusion process;
22 for example,
the link between the two source nodes
in Figure 1a does not benefit subse-
quent diffusion. With the increment
of source nodes, there is a strong likeli-
hood that some might cluster together,
as outlined in Figure 1a, thus decreas-
ing the effective diffusion links. But
such a negative effect is unlikely to
show up in Figure 1b unless there are
more initial source nodes.
Community structure. Global diffusion in a network with community
structure is restricted by intercommunity links;
16 that is, global diffusion
is facilitated only when the nodes on
the intercommunity links (also called
“bridge nodes” by network architects) are infected. In Figure 1a, four
nodes—“A,” “B,” “C,” and “D”—are
bridge nodes. The global diffusion is
suppressed temporarily because “D”
remains susceptible at t = 8. Although
“D” is not infected by “C” in Figure 1b,
the other source node initiates new
propagation in other communities, enhancing global diffusion.
Based on two factors—effective
diffusion links and community structure—the two diffusion processes—
maximum-degree-based and minimum-degree-based—in Figure 1a and
Figure 1b might result in a crossover
in terms of diffusion scale. The diffusion scale of Figure 1b would be greater than the diffusion scale of Figure 1a.
Differing diffusion scales involve several questions: For example, do the most
connected users always drive information diffusion in social networks? If
not, what kind of influence would the
community structure have on the diffusion process? To answer, we simulated information diffusion in both
real-world and synthetic networks with
community structure to investigate the
potential crossover points of two diffusion processes.
Crossover in Terms of
Propagation Scale
Many real-world systems can be de-
scribed as networks; examples are
email, social, and technological. Here,
we select a benchmark university email
dataset and construct an interaction
network to demonstrate the influence
of two diffusion processes—maxi-
mum-degree-based and minimum-de-
gree-based—triggered by two kinds of
initial source nodes with greatest- and
least-degree centrality. The network
includes 1,133 nodes and 5,451 links.
9
The average degree and clustering coef-
ficient in the network are 9.62 and 0.25,
respectively. Specifically, the clustering
coefficient is used to denote the degree
to which the neighbors of a user know
potential communities,
21 model diffu-
sion dynamics,
6 and control informa-
tion dissemination and sharing19). In
particular, the influence of each node
in the diffusion process must be taken
into consideration. In simulation ex-
periments, the source nodes that trig-
ger diffusion are selected by researchers
at random from a network or based on
predefined measures of centrality.
In recent decades, multiple centrality measures have been proposed to
statistically evaluate the importance
or influence of a node (such as degree,
2
betweenness,
11 coreness,
14 and eigenvector3). Degree is used mainly for
characterizing the partial influence of
a node.
2 Betweenness reflects the potential power of a node in controlling
information flow.
11 Coreness implies
that if a node lies in the core part of
a network, the node is more important.
14 And eigenvector accounts for
two factors: a node’s connections and
its neighbors’ influences.
3
State-of-the-art studies have looked into nodes
with relatively greater centrality in
information diffusion. However, the
influence of nodes with relatively less
centrality on the diffusion process has
never been completely addressed. In
this article, we aim to explain the importance of two kinds of nodes in the
information-diffusion process in a
community-based network. Our findings can help network administrators
better understand the diversity of communities and associated complexity of
the diffusion process.
Potential for a Crossover
Centrality characterizes the influence
of a node or user in a network. Intuitively, nodes with relatively greater
centrality should be more important
than those with relatively less centrality,
as they can lead to fast, large-scale
diffusion. However, we often find
diffusion breaks out from a group of
nodes with relatively less centrality in
the real world.
Figure 1 outlines two diffusion
processes as triggered by different
initial states in a community-based
network. The dotted circles represent
different communities in a network.
With a strong community structure,
the density of the intracommunity
links is much greater than that of the
intercommunity; for instance, only one
key insights
˽ Central users do not always contribute to
information diffusion due to a crossover
point of two diffusion processes triggered
by source users with most and fewest
connections, respectively.
˽ A strong community structure decreases
the stability of the crossover point in terms
of influence of two diffusion processes.
˽ Compared to the influence of community
structure on the diffusion process,
the increment of source nodes leads
the diffusion scale to the appearance
of an earlier crossover point.