Communications of the ACM

we conducted more simulations, as we explore in two real-world networks in the next section.

Nonlinear Crossover Phenomenon

To obtain a deeper understanding of such a phenomenon, we simulated propagations in real-world networks:

Datasets. We included two real-world networks with a potential community structure—a U.S. political weblog network (PolBlogs) 1 and a scientific collaboration network ( Arxiv). 18 The PolBlogs network includes 1,490 nodes and 19,025 links. Its average degree and clustering coefficient were 22. 44 and 0.36, respectively. Two political communities represent liberal blogs and conservative blogs, respectively. 1 Mark Newman of the University of Michigan analyzed the Arxiv network, with 56,276 nodes and

631,632 links, 18 looking to identify community-based features on co-authorship patterns. The average degree and clustering coefficient of the Arxiv networks were 11. 23 and 0.69, respectively, and the overall Arxiv network included 42 communities.

Experimental settings. The initial proportion of source nodes we denote as i0 varied from 0.01 to 0.5 and was divided into two parts. When the initial proportion is between 0.01 and 0.05, the rate of increase increases by 1%, after which the rate of increase increases to 5%. We selected the initial source nodes based on four kinds of centrality measures: degree, 2 betweenness, 11 k-core, 14 and eigenvector. 3

Experimental results. Under the same experimental conditions as outlined in the previous section, two propagation processes are triggered by source nodes with relatively greatest and relatively least centrality. Our focus is still on the critical crossover points. Since they are relevant to the time steps of each propagation, we recorded the time each crossover point emerged and normalized them based on tc/2000, where 2,000 was the total time steps, as is plotted in Figure 3. Despite different centrality measures and networks, the figure reveals several similarities:

Propagation scale. The crossover in terms of propagation scale emerges when the initial proportion of source nodes is low (such as 1%). Experiments on different kinds of networks show that a stable state, when the crossover phenomenon can be triggered, is indeed possible when i0 increases;

Crossover points. The time of different crossover points is generally a decreasing function of the initial proportion of source nodes i0; that is, the crossover points come earlier with the increment of the initial source nodes; and

Strength of community structure. The different crossover points under the same degree of centrality reveal the strength of influence a community structure exerts on the propagation process.

Experimental results in real-world
networks demonstrate our assumption
that central users (or nodes with rela-
tively greatest centrality) do not always
drive information diffusion. Specifi-
cally, the crossover phenomenon pre-
tion process, triggered by minimum-
degree nodes, leads to a larger scale of
diffusion until the whole propagation
system is stable. The maximum differ-
ence is reached numerically at time t2,
even exceeding that of time t1. The time
tc is the exact crossover point of the two
propagation processes in Figure 2.

During the propagation process, the most important period is between t1 and t2 when the two potential propagation processes undergo different transitions. The phenomenon in Figure 2 shows that, compared to nodes with relatively greater centrality, those with relatively less centrality could ensure the stability of propagation, reflecting its vital role in long-term diffusion. Such an interesting phenomenon also implies that in some cases, even central users may not always drive information diffusion. To validate this assumption,

Figure 2. Crossover of two propagation processes in terms of propagation scale in a university email network.

Time tc represents the critical moment the crossover begins, indicating nodes with relatively greater centrality do not always drive diffusion.

tc t1 t2

(a)

tc t1

t2

1 10 100 1000

2

4

6

8

10

12

Maximum degree Minimum degree

P ropag a t ion sc ale

X102

1 10 100 1000 – 1

0

1 X102

Propagation step (t) Propagation step (t)
N
u
me
r
i
ca
l
d
if
fere
n
ce
o
f
t
wo
p
rop
aga
ti
on
s
ca
les
(b)

Figure 3. Nonlinear crossover phenomenon in networks with community structure.

Each point represents the potential crossover point in terms of propagation scale. The results indicate both community structure and initial proportion of source nodes have influence on such phenomena.