This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE/ACM TRANSACTIONS ON NETWORKING

1

Modeling and Analysis of Conflicting Information
Propagation in a Finite Time Horizon
Jie Wang , Student Member, IEEE, Wenye Wang, Fellow, IEEE, and Cliff Wang Fellow, IEEE
Abstract— Emerging mobile applications enable people toconnect with one another more easily than ever, which causes networked systems, e.g., online social networks (OSN) and Internetof-Things (IoT), to grow rapidly in size, and become more
complex in structure. In these systems, different, even conflicting
information, e.g., rumor v.s. truth, and malware v.s. security
patches, can compete with each other during their propagation
over individual connections. For such information pairs, in which
a desired information kills its undesired counterpart on contact,
an interesting yet challenging question is when and how fast
the undesired information dies out. To answer this question,
we propose a Susceptible-Infectious-Cured (SIC) propagation
model, which captures short-term competitions between the twopieces of information, and define extinction time and half-life
time, as two pivots in time, to quantify the dying speed of
the undesired information. Our analysis revealed the impact of
network topology and initial conditions on the lifetime of theundesired information. In particular, we find that, the Cheeger
constant that measures the edge expansion property of a network
steers the scaling law of the lifetime with respect to the network
size, and the vertex eccentricities that are easier to computeprovide accurate estimation of the lifetime. Our analysis also
sheds light on where to inject the desired information, such thatits undesired counterpart can be eliminated faster.
Index Terms— Information propagation, conflicting information, epidemic models, network dynamics.

I. I NTRODUCTIOND

UE to proliferating mobile devices and emerging mobile
applications, people are more connected with each otherthan ever. Consequently, networked systems, such as onlinesocial networks (OSN), institutional computer networks, andInternet-of-Things (IoT), are developing into much larger andmore complex structures than before. For instance, the OSN
giant Facebook has 1.6 billion daily active users, who generate
more than 4 PetaByte new data every day [1], while thenumber of IoT devices is expected to exceed 500 billion by
2030 [2], imposing a tangible impact on mobile data traffic.
As more and more individuals, e.g., users in OSN, and devices
Manuscript received October 11, 2017; revised August 19, 2018;
accepted January 24, 2020; approved by IEEE/ACM T RANSACTIONSON N ETWORKING Editor E. Yeh. This work was supported in partby the NSF under Grant CNS1423151 and Grant CNS1527696 andin part by the ARO under Grant W911NF-15-2-0102. This article
was presented at the IEEE INFOCOM 2016. (Corresponding author:
Jie Wang.)
Jie Wang and Wenye Wang are with the Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC 27606 USA(e-mail: jwang50@ncsu.edu; wwang@ncsu.edu).
Cliff Wang is with the Army Research Office, Research Triangle Park,
Raleigh, NC 27709 USA (e-mail: cliff.wang@us.army.mil).
This article has supplementary downloadable material available at
http://ieeexplore.ieee.org, provided by the authors.
Digital Object Identifier 10.1109/TNET.2020.2976972

in IoT, join such systems, inconsistent, even conflicting information are injected into the network, leading to an interesting
competition among different pieces of information.
By conflicting, we mean two pieces of information that can
not be admitted by the same individual at the same time.
For example, it is highly unlikely, if not impossible, for an
OSN user to simultaneously admit the truth and a rumor that
contradicts with the truth. Particularly for such pairs, in which
one piece (the desired information, e.g., truth) is apparently
more credible than the other (the undesired information, e.g.,a rumor), an individual who has chosen to admit the desired
information, will not be affected by its undesired counterpart.
Therefore, the undesired information, spreading via individual
connections itself, will be eliminated from the network (dieout) by its desired counterpart, given sufficient time. In otherwords, the competition between the conflicting information
pair takes place in finite time. Naturally, we ask: when, andhow fast will the undesired information die out?
A. Motivating Examples
The phenomenon of conflicting information propagation isprevalent in OSNs, which has become the arena of clashing
opinions, unverified reports, and publicity campaigns. For
example, after the Boston bombing incident on April 15th,
2013, Reddit users started an online suspect hunt, which identified an innocent person as the bomber [3]. This rumor (undesired information in the form of image data) spread rapidly on
both Reddit and Twitter, leading to serious cyber-harassment
to the wrongly-accused. The number of mentions regarding
this rumor quickly decreased after the police released thecorrect information (desired information) [4]. Before the rumor
dies out completely, its impact, harassment to the wronglyaccused, as well as posts and clicks from users, will not
disappear, so answer to the ‘when and how fast’ question
directly characterizes the data traffic in the system over time.
On the other hand, such competing-while-spreading phenomenon can also be observed in engineered systems, such as
computer networks for an institution, and IoT. For instance,
to eliminate a computer malware (undesired information in
the form of source code), such as SMS Trojans [5] thatspreads over emails and messages, and Chameleon [6] thatspreads over WiFi links, the system administrator can distribute self-replicable security patches (desired information) to‘cure’ malware-infected devices, and ‘immune’ devices thathave not been reached by the malware. In IoT, on the other
hand, faults (undesired information) can quickly propagate dueto the interdependence of data/power between devices, leading
to a cascade-of-failures, while restoration operations (desired

1063-6692 © 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See https://www.ieee.org/publications/rights/index.html for more information.

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
2

information) on some devices, e.g., load-shedding, will also
trigger/enable the recovery of faulty devices that are connected
to restored devices, gradually bringing the system back tonormal operations. In these examples, desired information isproactively injected by the administrator as a countermeasureagainst malware or cascade-of-failures. In this sense, answer tothe ‘when and how fast’ question also measures how effective
a countermeasure is, in controlling the undesired informationfrom epidemic spreading.
These conflicting information propagation processes have
two defining characteristics: First, there are two pieces of
information circulating the same network, both spread via contacts of individuals in an epidemic manner. Second, the laterinjected desired information can convert victims of the undesired information back to normal states, just like a replicable
antidote can cure/immune an individual from an infectious
virus, as a result of which, the cured/immune individual will
not be infected by the same virus again, but not vice versa.
Our objective is to find out when and how fast the virus diesout in the network, after the injection of antidotes.
B. Related Work
Considering the resemblance between information spreadover individual connections, and virus spread over individual
contacts, information propagation has been extensively studied
via epidemic models, in which information is modeled as aninfectious virus. Based on the number of information pieces
considered, existing literature can be broadly categorized into
single-virus epidemics, and competing epidemics. However,none of existing approaches can describe the short-term competition between the virus and antidote.
Existing research on single-virus epidemics focus on propagation model [7], [8], epidemic threshold [9], [10], dependency
on network topology [11]–[13] and epidemic control with
non-self-replicable antidotes [12], [14]. However, these models
only consider one piece of the information in the spreading
process, and are hence not applicable to our problem. In fact,a single-virus epidemic is a special case of the conflicting
information propagation process discussed in this paper, in thesense that the virus spreads to every corner of the network,and lives forever without any injection of antidote.
With respect to competing epidemics between conflicting
information, existing literature can be further categorized into
population dynamics and network dynamics [15], depending on whether network topology is taking into consideration. In population dynamics, participants of the propagation
process are assumed to be a well-mixed population, i.e.,there is no notion of network, which does not apply to mostpropagation scenarios. In contrast, network dynamics view
participants of the propagation process as heterogeneous, andmodel their connections with a graph structure. Among these,
Lin et al. [16] utilized Mean-Field Approximation (MFA) to
conduct asymptomatic and numerical analysis of the propagation process. Prakash et al. [17] proposed an SI1 I2 S model,
and proved that a piece information with faster propagation
speed will eliminate its slower counterpart as time approaches
infinity. More recently, Dadlani et.al.. modeled competingmemes as epidemic processes on multi-layered graphs, andIEEE/ACM TRANSACTIONS ON NETWORKING

derived critical survival threshold of a meme [18] to bepersistent. Newman [19] found the coexistence threshold of
two competing epidemics on networks with known degree distributions, under Susceptible-Infected-Recovered (SIR) model.
From the perspective of propagation model, both the linear
threshold model and SI1 I2 S model allow any individual toswitch back and forth between different information, in which
context the asymptotic behavior (steady state of the system
as time t → ∞) of the dynamics is of more interest. In ourcase, however, the desired information is much more credible
than its undesired counterpart, so competition between the two
finishes in finite time. Consequently, the answer to our researchquestion depends on transient changes of individual states,
to which existing analysis on asymptotic behavior does not
apply.

C. Summary of Contributions
Seemingly simple, the when and how fast question is
actually challenging because of the short-term competition
between conflicting information, and the possibly complex
network topology of the system. First, answer to this question
depends on occurrences of transient events, analysis of which
involves time and is hence difficult. Second, the underlying
network can be large, complex, or both, considering the broad
applications of this problem, for which simple propagation rule
at node level gives rise to complicated behavior of the system
as a whole. Therefore, we need to identify useful topologicalproperties of the network that can best answer the question,
but are also accessible in practice for complex networks.
To address these challenges, contributions of this paper canbe summarized as follows.
1) Modeling: We propose a novel SIC propagation model,
to capture the competing and epidemic nature of a conflicting information pair in their propagation processes.
2) Metrics: We define new metrics, namely the extinction
time τe and half-life time τ 12 , as two pivots in time,to quantify how fast the virus dies.
3) Findings: We derive bounds of the expected extinction
time E(τe ) and half-life time E(τ 12 ) for network G withan arbitrary topology, and find that:nBoth E(τe ) and E(τ 12 ) are O( logη(G) ), where n is
the network size, and η(G) is the Cheeger constant measuring the level of bottleneck-ness of G.
It indicates that the undesired information dies out
slower in larger networks with bottlenecks (η(G) ≤O(log n)), e.g., networks with star topology. In contrast, the extinction time decreases with n whenη(G) is bounded below by log n.
• Considering η(G) is difficult to obtain (NP-hard)for general networks, we show that the lifetimeof the undesired information can also be upperbounded by functions of vertex eccentricities. Thesebounds enable us to estimate the extinction time inlarge complex networks, and also imply where to
inject desired information such that its undesired
counterpart can be eliminated faster.
•

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

The rest of the paper is organized as follows. First we
introduce the SIC propagation model in Section II, followed by
metrics definitions and problem formulation for a conflicting
information propagation process. Then we study SIC epidemics on networks of two special topologies, i.e., clique andstar, in Sec. III. Based on the observation of these preliminary
results, we identify two topological properties, namely, graphexpansion and vertex eccentricity, by which we derive bounds
for networks with arbitrary topology in Sec. IV, and provide
practical guidelines on selecting antidote recipients to control
the epidemic of undesired information. Finally, the paper isconcluded in Sec. V.
II. T HE SIC P ROPAGATION M ODELIn this section, we introduce terminologies, assumptions
and definitions of the Susceptible-Infected-Cured (SIC) propagation model, to capture the competition between a pair ofconflicting information, referred to as a virus and an antidote,
both of which propagate in an epidemic manner. This dynamic
process takes place in a network, whose vertices represent individuals, e.g., devices in IoT, and edges represent connections,e.g., wireless links between devices. Based on the SIC model,
we then formally define metrics to quantify the dying speedof the undesired information (virus), as the expected answers
to the proposed when and how fast questions.
A. Conflicting Information Pair: Virus x and Antidote ax
Conflicting information has been defined as “two piecesof text that are extremely unlikely to be considered true
simultaneously” in relevant information collection studies [20].
Considering that information takes various forms other thantext, such as source code, operating status of devices, andcommands, we extend this definition to mutually-exclusive
information that can not be possessed/admitted by the same
individual at the same time. Particularly, we focus on a virusantidote pair, in which the desired information (referred to as
antidote ax ) is of dominant credibility/power over its undesired
counterpart (referred to as virus x), such that it kills the virus
if they are both present on the same vertex, but not vice versa.
Note that virus x can not re-infect an individual, who has
admitted antidote ax , which is different to the symmetricsetting in existing models [17], [21], where virus x can
re-infect an individual who already has ax , so ax is treatedas another virus, instead of an antidote to x. The rationale
behind the asymmetry in our model comes from observations
in real-world examples and concerns on modeling accuracy.
First, for the case of security patch v.s. computer malware, andrestoration commands v.s. (cascading) faulty status, the desired
information (e.g., security patch) is injected purposely by thesystem to eliminate the undesired information (e.g., malware),and it is only reasonable that a malware can not leverage afixed bug to attack the system. Second, for the case of clashing
opinions and adoption of different products, once an individual
is convinced (infected) by the newer and better product ax ,it is unlikely for him/her to switch back to the older productx, unless the older product has an upgrade (to the newest
version) bx . This new injection of bx is considered as theFig. 1.

3

State transitions of the SIC epidemic model.

beginning of a new epidemic process with bx as the antidote
to virus ax in our model. In the SI1 · · · Ik S model, bx andx are considered as the same virus competing with ax , suchthat re-infection (or switching-back from ax to x) is allowed,
because of its focus on long-term (time t → ∞) behaviors.
A drawback of the existing approach, e.g., [17], [21], is that bx
and x are automatically associated with the same propagation
speed. Our approach, on the contrary, allows x, ax , bx to havedifferent propagation speeds, capturing competitions of bothax v.s. x, and bx v.s. ax , and is hence more accurate.
B. Network Model G(V, E)
The network is described as a graph G(V, E), where vertex
set V corresponds to the set of individuals in the system, andedge set E corresponds to the set of connections between anyof two individuals. An edge e(i, j) exists when vertex i andj can directly exchange information. For any vertex v ∈ V,
its neighborhood N (v) := {u ∈ V| (u, v) ∈ E} is definedas the set of vertices that is directly connected to vertex v.
We make the following assumptions of the network G: i) It
is undirected, that is, edge e(i, j) = e(j, i) identifies mutual
connections between vertices i and j. ii) It is connected, suchthat information (x and ax ) can spread to every vertex in V.
iii) It is static, that is, both size n := |V| and topology of the
network remain the same during the epidemic evolution.
C. Epidemic Propagation Process
Both virus x and antidote ax spread in an epidemic manner.
To describe this epidemic process, each vertex is associatedwith a state that can change over time.
1) State Transitions: Let r.v. Xvx (t) : Ω → Λ = {0, 1, −1}
denote the state of vertex v ∈ V at time t. Values of Xvx
correspond to different nodal states, as shown in Fig. 1.
Susceptible at time t: The default state Xvx (t) = 0 (whitecircle with letter S in Fig. 1 indicates that neither the virus
x nor the antidote ax has reached vertex v by time t, so it ispossible for v to be infected by x, or cured/immunized by ax
in the future, if any of them propagates to v via contacts.
Infected at time ti : If a copy of virus x reaches susceptible
vertex v at ti , v becomes infected at ti , which means Xvx (ti ) =1 and limt→t− Xvx (t) = 0. This infect action is shown by theidashed arrow from susceptible state to the infected state (redcircle with letter I) in Fig. 1. At this state, vertex v will try
to infect, i.e., pass copies of virus x to any of its susceptibleneighbors, that is, u ∈ NSx (ti , v) = {u ∈ N (v)|Xux (ti ) = 0},

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
4

Fig. 2.

IEEE/ACM TRANSACTIONS ON NETWORKINGAn example of an SIC epidemics on a network of 12 vertices.

Fig. 3. Illustration of the extinction time τe and half-life time τ 1 of the2virus for the example shown in Fig. 2: At time t0 , C0 = 1 copy of antidote
is injected into the network.

after a random period of time sxv (u). Vertex v will stay ininfected state until it receives a copy of antidote ax .
Cured at time tc : If at tc , a copy of antidote ax reaches
vertex v (solid arrows in Fig. 1) for the first time, i.e.,
limt→t−Xvx (t) ≥ 0, the state of v changes to cured at tc ,cthat is, Xvx (t) = −1, as shown as the blue circle with letter C
in Fig. 1. At this state, vertex v will pass copies of antidote to
any u of its neighbors NNx C (t, v) = {u ∈ N (v)|Xux (ti ) ≥ 0}
after a random period of time sav x (u). Vertex v will stay cured
for the rest of the time, i.e., Xvx (t) = −1 for any t > tc .
Fig. 2 shows an example of a simple network with 12 vertices under an SIC dynamics. As shown in Fig. 2(a), before
antidote ax is injected into the network at time t0 , verticesin {v1 , v2 , v3 , v5 , v9 , v11 } are infected (colored in red). Thenat t0 , one unit of antidote is given to vertex v8 , and cures it
immediately (indicated as blue), as shown in Fig. 3(b). As time
t proceeds, states of the 12 vertices change in Fig. 3(c-e).
Eventually, the virus dies out at time t = t0 + τe .
2) Propagation Rules: Individual state changes are driven
by the propagation of virus x and antidote ax , whose
speeds are controlled by intervals {sxu (v)}v∈NS (t,u) and{saux (v)}v∈NN C (t,u) . To make this problem tractable, we follow the convention in [13], [17] and assume time homogeneity
for the propagation process: For any vertex u, random intervals{sxu (v)}v∈NS (t,u) and {saux (v)}v∈NN C (t,u) are two groups ofr.v.’s satisfying i) pairwise independent; and ii) exponentiallyxxand γu,v, respectively.
distributed with parameters βu,vxxFrom the perspective of time, βu,v = βv,uis known as thexxvirulence (or infection rate) of virus x, while γu,v
= γv,uasthe curing rate of antidote ax , representing how frequently acopy of virus x and antidote ax is exchanged via edge e(u, v),
respectively. We give their formal definitions as follows.

Definition 1: For an infected vertex u, and a susceptible
vertex v ∈ NSx (t, v), the virulence of virus x on edge e(u, v)
is defined as
P(sxu (v) ≤ t)
x
βu,v
,
(1)
:= limtt→0+where sxu (v) is the time period between the infection of u,
and the time when u passes a copy of virus x to v vie edgee(u, v).
Definition 2: For a vertex u in cured state, and its neighborv ∈ NNx C (t, v), the curing rate of antidote ax on edge e(u, v)
is defined as
P(saux (v) ≤ t)
x
γu,v
,
(2)
:= lim+tt→0where saux (v) is the time period between the curing of u, andthe time when u passes a copy of antidote to v vie edge e(u, v).
x
From the perspective of probability, βu,v
is also known
as the infection probability over unit time, which can be
explained by considering a simple network composed of twoconnected vertices, i.e., V = {u, v}. At time t, given Xvx (t) =0, the probability that v gets infected by u in Δt is
P Xvx (t + Δt) = 1|Xvx (t) = 0x· 1{Xux (t)=1} + o(Δt),= Δt · βu,v(3)xwhere r.v. sxu (v) ∼ Exp(βu,v), with mean E(sxu (v)) =1. Similar results also apply to r.v. saux (v) and curx
βu,vx
. Therefore, when the time interval is of unit
ing rate γu,v
length, i.e., Δt = 1, thestate transition probability P Xvx (t +xequalsΔt) = 1|Xvx (t) = 0 = P(sxu (v) ≤ t) = βu,vx
to the infection rate βu,v in value, which bridges the gap
between continuous-time modeling/analysis and discrete-time
simulations.
At any time t, vertices set V = S x (t)∪I x (t)∪C x (t), wherex
S (t), I x (t), C x (t) are mutually disjoint sets: the susceptible
set S x (t) := {v ∈ V : Xvx (t) := 0}, the infected setI x (t) ={v ∈ V : Xvx (t) := 1}, and the cured set C x (t) = {v ∈V : Xvx (t) = −1}. Evolution of an SIC epidemic process
can be captured by the time-varying infection count, I x (t) :=|I x (t)|, and the cured count, C x (t) := |C x (t)|. For the ease ofnotation, we suppress x in Xvx (t), S x (t), I x (t), C x (t), andwrite Xv (t), S(t), I(t), C(t) instead.

D. When and How Fast Will the Virus Die Out?
From the state transition diagram (Fig. 2) of the SIC
epidemics and the fact that network G is connected, it is clear

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

that eventually the virus will be eliminated from G, i.e., as timet → ∞, state Xv (t) = −1 for every vertex v. The question iswhen and how fast the virus dies out. In other words, we needto examine short-term transitions of individual states, which
all take place in finite time. To answer this question, we define
two pivots in the lifetime of virus x to quantify its dying speed.
Definition 3: For an SIC dynamic of virus x and antidote
ax , the extinction time of virus x, denoted as τe , is definedas the length of the time interval between t0 and the first timethat the infected set I(t) becomes empty, that is,τe := inf{t > t0 : I(t) = φ} − t0 ,(4)

where t0 is the time instant when C0 copies of antidote ax
are injected into the network G.
The extinction time τe is a finite1 r.v. on measurable spacen(Ωn , 2Ω , P). It answers when the virus dies out, because time
instant t0 + τe marks the end point of the virus’s life in G.
In other words, the infection count decreases from I(t0 ) to
0 during a time interval of length τe , so we know the virus
0)(undesired information) dies out at an average speed of I(tτe .
But it is still not clear how such speed changes during the
lifetime of the virus, i.e., how fast the virus dies out, whichanswers a lot of realistic questions, e.g., when will the majority
of individuals be free of the undesired information? To answer
this question, we identify another pivot in time.
Definition 4: For an SIC dynamic of virus x and antidote
ax , the half-life time of the virus epidemic, denoted as τ 12 ,is defined as the length of the time interval between t0 andthe last time that event {I(t) ≥ 12 I(t0 )} happens after t0 , that
is,


1
τ 12 := sup t ∈ [t0 , t0 + τe ] : I(t) ≥ I(t0 ) − t0 , (5)2where I(t0 ) > 0 is the initial infection count at t0 .
The Half-life time τ 12 : Ωn → [t0 , t0 + τe ] is also a finite r.v.
on the same measurable space as r.v. τe . The term half-life isoriginally from Chemical Kinetics, which describes the decayof discrete entities. But, unlike in Chemical Kinetics, where
half-life is the mean, we define half-life as the actual timeinterval until event {I(t) ≥ 12 I(t0 )} happens for the last time.
The physical meaning of τ 12 can be explain as follows: thecompetition between the undesired information and its desired
counterpart mainly takes place before pivot time t0 + τ 12 , after
which the undesired information can be viewed as controlled,because the number of its victim will never exceed thethreshold I(t0 )/2.
In this sense, the two lifetime metrics, extinction timeτe and half-life time τ 12 , illustrate how fast the virus dies,because for a fixed initial condition (I(t0 ) and C(t0 )),the larger the gap τe − τ 12 , the faster the undesired information dies during its most hazardous phase [t0 , t0 + τ 12 ].
Consequently, if desired information is purposely injectedby the system as a countermeasure against the undesired
information, its effectiveness can be reflected by these lifetime
metrics.
1 To be more accurate, r.v. τ is almost surely (a.s.) finite, that is, P(τ <ee∞) = 1, when the network G is connected, because it can be written as thesummation of a finite number of exponential r.v.’s, each of which is a.s. finite.

5

Fig. 3 illustrates the extinction time and the half-life time
for the example of the SIC dynamics shown in Fig. 2, wherea red arrow corresponds to an infection, and a blue one
represents a curing event. At t0 +τ 21 , the infection count of thesystem drops to 3 (= 12 I0 ), and never exceeds 3 again, which
implies that the virus epidemic has been restricted to a limitedarea, or equivalently, under control. At t0 + τe , the virus diesout.
Without loss of generality, let t0 = 0, and denote I(0)as I0 (and C(0) = C0 ) for the ease of notation. All theevents we discuss hereafter take place in the observation
window [0, τe ]. We further assume that both the infection rate
β and curing rate γ are constant on every edge of the network, which is commonly adopted in information propagation
studies.
Under the proposed SIC model, we restate our researchquestion as follows: Consider a pair of conflicting information(x, ax ), in which x is the virus with virulence β, and ax isthe antidote with curing rate γ. At time t = 0, C0 copies
of antidote are distributed in network G(V, E), when theinfection count equals to I0 . What is the expected extinction
time E(τe ) and half-life time E(τ 12 ) of virus x (undesired
information)?
III. C ONFLICTING I NFORMATION P ROPAGATION IN
C OMPLETE N ETWORKS AND S TAR N ETWORKS
There are three sets of defining factors, which control the
spreading behavior and hence the lifetime of the undesired
information in an SIC dynamics: propagation parameters(β, γ), initial condition (I0 , C0 ), and topological propertiesof network G. Among these, the key challenge arises fromthe underlying network G, a structure with numerous topological properties, some of which are of particular importance to the epidemic spreading of information, as evidenced
in [11], [13], [19]. To answer the when and how fast question
for conflicting information propagation in an unspecified,and possibly complex, network G, we start from simple
cases, in which G has special topologies, in order to clarify
which topological properties to consider for more generalcases. Specifically, we examine complete graph Kn and stargraph Sn , which are not only common network topology themselves, but also essential components of complex networked
systems.
A. SIC Epidemics on Complete Networks Kn
A complete graph Kn , is a fully connected graph with nvertices, in which for any pair of vertices vi , vj ∈ V (Kn ), i =j, there exists an edge e(i, j) ∈ E(Kn ) between them, andhence |E(Kn )| = n(n−1)/2. This topology is frequently seenin networks that require high reliability, e.g., network of AS
routers, or networks that are densely connected everywhere,e.g., a household or a community, where every individualis familiar with one another. It has two key characteristics:i) it is the most densely connected simple graph, because
it has the maximum number of edges; ii) it is regular,
because every vertex is inter-changable with another, whichmeans they have the same vertex metrics, such as degree andAuthorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
6

centrality. In such networks, the expected lifetime metrics of
the undesired information are upper bounded by the following
theorem.
Theorem 1: Consider an SIC dynamics in action on acomplete network Kn , with curing rate γ, and initial condition(I0 , C0 ). The expected extinction time E(τe ) and half-life timeE(τ 12 ) of the virus can be bounded above as1(n − 1)(n − C0 )E(τe ) <,(6)
2 + lnγnC0(n − 1)(n − 1 − I0 /2 )1
2 + ln; (7)E(τ 12 ) <γn
I0 /2 + 2
when C0 ≥ 2, we also have2
E(τe ) <ln(n − C0 ),(8)γ(n − 1 + C0 )2n − C0E(τ 12 ) ≤1 + ln,γ(n − 1 − I0 /2 + C0 )I0 /2 + 1
(9)where n = |V| is the size of the complete network Kn .
Proof of Theorem 1 can be found in Appendix A.
Theorem 1 implies that both the expected extinction timeand half-life time decreases with size n of the clique asO( logn n ), which means the larger the network, the quicker
the undesired information dies, given the same initial condition of the dynamics. The reason behind this is that, denseconnections among vertices make it difficult for the virus tododge contact with antidotes. In other words, even thoughboth virus and antidote can spread faster due to the large
number of edges, dense connections work in favor of theantidote propagation. On the other hand, with respect to thesevereness of virus infection upon antidote injection, we cansee the half-life time decreases with the initial infection countI0 as O(log IA0 ), where A is a function of n and C0 that
does not vary with I0 . It shows that the severer the infection,
the less time it takes to get the virus epidemics under control.
In this case (larger I0 ), the larger gap τe − τ 12 indicatesthat competition between the antidote and the virus is only
fierce for a short period of time, and the larger portionof extinction time is spent on extinguishing cornered virus
infections.
From the perspective of connectivity, any other simple
network topology of the same size n has strictly less edges
than the complete graph Kn , as a result of which the undesired
information (virus) will die slower with high probability inthese networks, even with the same initial condition (I0 andC0 ). Bases on this observation, we also have the following
lower bounds as a corollary of Theorem 1.
Corollary 1: For an SIC epidemic with curing rate γ on anarbitrary network G of size n, the expected extinction timeand half-life time of the virus can be bounded below as
1
HC0 +I0 −1 − HC0 −1 + Hn−C0 − Hn−C0 −I0 ,E(τe ) ≥γn(10)
1HC0 +I0 /2−1 − HC0 −1 + Hn−C0
E(τ 12 ) ≥γn(11)−Hn−C0 −I0 /2 ,IEEE/ACM TRANSACTIONS ON NETWORKINGkwhere Hk = j=1 1j is the k-th Harmonic Number.
Proof of Corollary 1 can be found in Appendix B.
B. SIC Epidemics on Star Networks Sn
As opposed to the most densely connected complete network Kn , a star network Sn is composed of a hub v1 andn − 1 leaves (peripheral vertices), such that every piece of
information from a leaf vertex has to go through the hub
to reach another vertex. In other words, edges only exists
between the hub and leaves, creating a huge bottleneck in the
middle, which can be viewed as a high-degree of heterogeneity
among vertices. The star topology is also of great importance,
due to its natural link to artificial structures, e.g., a WiFi
access network within the coverage of an access point, andthe ego-network of a high-degree node in OSNs.
Consider the same SIC dynamic with infection rate β andcuring rate γ on a star Sn . In an extreme case, if a copy ofantidote is first given to the hub, then infection count I(t)will be monotonically decreasing with time t, which is lessinteresting, because it is impossible for the virus to claim new
victims, and hence no competition. Therefore, we consider
the case that antidotes can only be distributed to peripheral
vertices at time 0, and present the following upper bounds.
Theorem 2: For an SIC dynamics on a start network inwhich the initial infection count satisfies I0 ≥ 2, the expected
extinction time E(τe ) and half-life E(τ 12 ) follow upper bounds:
1 1βE(τe ) <+ 1 + ln(I0 − 1) +, (12)γ C0
γC0 (I0 − 1)β
1 1
I0 − 1)+. (13)+ 1 + ln(E(τ 12 ) <
γ C0
I0 /2
γC0 (I0 − 1)
Proof of Theorem 2 can be found in Appendix C.
It is intuitive that the undesired information (virus) will die
slower in a star network than in a complete network of thesame size, due to the much sparser connections. However,
it is rather interesting to observe from Theorem 2 that, boththe expected extinction time and half-life time increases with
the network size n in the star topology. This clear contrast
between the two topologies leads to a conjecture: existenceof bottlenecks changes how the network size impacts whenand how fast the virus dies out. In addition to this difference,
we also observe a similarity with SIC epidemics on thecomplete network, that is, the half-life time of the virus ina star network also decreases with the initial infection count
I0 , but with a milder decreasing slope, as O( I10 ).
C. Numerical Simulation and Discussion
To validate upper bounds (dashed lines) in Theorem 1 andTheorem 2, numerical results (solid lines with markers) withrespect to network size n and the initial infection count I0 are
shown in Fig. 4 and Fig. 5-6 respectively. As can be seen fromall three figures, trends of both the expected extinction timeand half-life time are well captured by the derived bounds.
Comparing the bounds and simulation results for the two
simple topologies, we highlight the following observations.

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

1) Propagation Parameters β and γ: The infection/curing
rates have the same effect on both temporal metrics regardlessof network topology, which can be observed by comparing
the sub-figures in Fig. 5 and Fig. 6. To be more specific, they
only lengthen or shorten time intervals between events, butdoes not change the order of event occurrences, resulting in a
homogeneous scaling effect on both lifetime metrics.
2) Network Size n: There is a clear dichotomy in the
dying speed of the virus with respect to the network sizen, that is, virus dies faster in a larger complete network,
but dies slower in a larger star network, as shown in thesemi-log plots of Fig. 4. Both E(τe ) and E(τ 12 ) are O( logn n )for complete networks (decreasing blue lines), while both are
O(log n) for star networks (increasing red lines), as indicatedby Theorem 1 and Theorem 2, respectively. This implies aninteresting change in the conflicting information propagation
process, when a hub (bottleneck) emerges in the network.
3) Initial Infection Count I0 : Impact of I0 on the lifetimeof the virus is shown in Fig. 5 and 6, for complete network
K100 and star network S100 , respectively. The mild zig-zag
pattern of the half-life time (left end of all blue solid lines
with markers) is caused by rounding-off the threshold I10
when I0 is small. Though the general trend is the same inboth types of networks, i.e., extinction time increases with I0 ,while half-life time decreases with I0 , impact of topology is
still apparent, as indicated by the different scaling behavior
over I0 (black texts in Fig. 5 and 6).
As two extremes of network topology, the complete graphis regular (every vertex has the same degree) and most densely), while the star graph is highly
connected (|E| = n(n−1)
2irregular (due to the existence of the central hub) and sparse(|E| = n − 1). Comparing the two, we observe when edges
concentrate and form a bottleneck in the network, the impact
of network size n and initial condition I0 changes drastically.
Though results in these two simple networks do not directly
apply to general cases, they shed lights on studying conflicting
information propagation in general networks, by recognizing
the importance of bottlenecks in networks.
IV. C ONFLICTING I NFORMATION P ROPAGATION IN
N ETWORKS W ITH A RBITRARY T OPOLOGY
Considering the broad application scenarios of conflicting
information propagation, it is possible, and even more likely,that the underlying network G does not have nice topologicalproperties like regularity, and is hence a complex networkwith unique topologies. To study when and how fast theundesired information dies out in such networks, we examinegraph metrics, namely, the Cheeger constant η(G) and vertex
eccentricities {(v)}v∈V , to quantitatively link topologicalproperties to the lifetime metrics (E(τe ) and E(τ 12 )) of thevirus in an SIC epidemics through upper bounds.
A. Bounds by Considering the Edge-Expansion Property
Recall in the comparison between complete networks andstar networks, we find that the key to propagation behavior
change is the central hub of a star, which forms a bottleneckin the network. Therefore, we first consider the metric that

7

Fig. 4. Expected extinction time E(τe ) and half-life time E(τ 1 ) of an SIC
2epidemics (C0 = 1, I0 = 10), with respect to the network size n. In thissimulation, we set the infection(β) and curing (γ) rates as β = γ = 0.01 in
the star network Sn , and β = γ = 0.0001 in the complete network Kn , fora clearer comparison between the two topologies.

quantitatively measures the level of ‘bottleneckness’ of a
network G, the Cheeger constant η(G), which is defined as|δ(S)|
η(G) :=
inf|S| , where δ(S) := [S, V \ S] is theS⊂V,|S|≤n/2

edge-cut of vertex set S, that is, the set of boundary edges
between set S and its compliment set V \ S.
As a graph expansion property [22], η(G) identifies the‘narrowest’ part of network G, i.e., the minimum boundaryedges of as many as vertices. Intuitively, the larger theboundary set, the more difficult it is to break the network
into isolated components by disconnecting edges, so η(G)and other expansion properties are viewed as indicators ofrobustness, and hence studied in many applications [22].
Due to this property, it has been shown that η(G) is of
key importance to the spreading behavior of an epidemic
process, under different propagation models, including SI [13],[23], SIS [13], and SIR [11] models. For the proposed SIC
propagation model, in which two epidemic processes compete
in finite time, we show in the following theorem that both thelog n).
expected extinction time and half-life time are O( γη(G)Theorem 3: For a network G with Cheeger constant η(G),given the initial cured count C0 , the extinction time of thevirus in an SIC epidemic with curing rate γ can be bounded
above byE(τe ) ≤1[a ln(n + b) + c],
γη(G)

(14)

1) If 1 ≤ C0 < n/2, b = 0, and2when C0 = 1, a = ln2, c = 2γE ,4C0 −52otherwise a = ln 4(C0 −1) , c = − 8(C2 + γE ;0 −1)
12) If C0 ≥ n/2, a = 1, b = −C0 + 1, c = 2(n−C+ γE ,
0 +1)
where γE  0.577 is the Euler-Mascheroni constant.
When the initial infection count I0 is given, the expectedhalf-life time can be upper bounded2 when 2 ≤ C0 < n/2,1
4C0 − 5
2I0 + 1n2
E(τ 12 ) ≤
−
+
,
ln
γη(G)
2(C0 − 1)I0
8(C0 − 1)2I02(15)
2 For the case of C > n/2, it is with high probability that τ = 0, which102
is a less interesting case and hence not discussed.

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
8

IEEE/ACM TRANSACTIONS ON NETWORKING

Fig. 5.

Extinction time E(τe ) and Half-life time E(τ 1 ) in the complete graph K100 , over the initial infection count I0 .

Fig. 6.

Extinction time E(τe ) and Half-life time E(τ 1 ) in the star network S100 , over the initial infection count I0 .

2

2



2I0 +1
1n2
ln 2I.
and when C0 = 1, E(τ 12 ) ≤ γη(G)+2I0extinction time can be upper bounded by

0

Proof: Let Vk := {V |V ⊂ V, |V | = k} be the set of allvertex sets containing k vertices from the network G(V, E).
Let Ck ∈ Vk be the set of cured k vertices when C(t) = k.
Let Tk := inf{t|C(t) = k} be the time that the cured countC(t) reaches k. Note that C(t) is monotonically increasing,and C(0) = C0 , TC0 = 0. For any k ≥ C0 ,E(Tk+1 − Tk ) =E Tk+1 −Tk |C(t) = A)P(C(t) = A


A⊂Vk

=E

1
γ|δ(Ck )|,(16)

where δ(Ck ) := [Ck , V \ Ck ] is the edge cut of set Ck , andη(G)k, k < n2 ,|δ(Ck )| ≥η(G)(n − k), k ≥ n2 .
n−1Also, we have E(τe ) ≤k=C0 E(Tk+1 − Tk ) from
Lemma 3 in the Appendix. So when 2 ≤ C0 < n2 , the expectedE(τe )

≤

n/2

k=C0

n−1

1
1
+
γη(G)kγη(G)(n − k)nk= 2 +1

2
1=
2H n2 − − HC0 −1
γη(G)
n

F ranel
4C0 − 51n2−<
− γE ,ln
γη(G)4(C0 − 1) 8(C0 − 1)2
where the last line follows from Franel’s Inequality [24].
Similarly, the expected half-life time can be bounded byE(τ 12 ) ≤

n/2

k=C0

1
+
γη(G)kn−1−I0 /2



k= n
2 +1

1
.
γη(G)(n − k)As for the case of C0 ≥ n2 , the upper bound can be obtained
n−1
1.
by considering E(τe ) ≤ k=C0 γη(G)(n−k)

Though not a sharp bound, Theorem 3 confirms the importance of the edge-expansion property, i.e., the Cheeger constant η(G), in epidemic spreading of information, particularly
two pieces of conflicting information in this paper. As canbe seen, the more ‘expandable’ (strong connectivity withless vertices, towards the clique topology), the less time ittakes to eliminate the virus, which explains the shorter rumor

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

circulation time [25] than before, as OSNs (and Internet atlarge) become more connected nowadays. Particularly for thetwo simple network topologies, clique and star, studied in theprevious section, Theorem 3 clearly explains the dichotomyof the scaling laws over the network size n: i) η(Kn ) =n/2 = O(n), which implies the O( logn n ) scaling for thecomplete network Kn ; while ii) η(Sn ) = O(1) for the star
network Sn , and hence the O(log n) increasing over network
size n.
For some large networks with special topological properties [22], existing results on its edge expansion properties
allow us to estimate the lifetime of the undesired informationin such networks as the network grow in size. For instance,
Krishnasamy et.al. showed that for random graphs (Erdösn, there is a highRényi graphs) G(n, p) with p > 32 log
4np
1
probability (over 1 − n2 ) that η(G) ≥ 4 [13, Corollary 2].
Applying Theorem 3, we know that the undesired information
dies out in O( logn
γn ) time with high probability.
For a complex network with arbitrary topology, however,obtaining the Cheeger constant is a well-known hard problem(NP-hard [26]), especially when the network is large. In thiscase, η(G) can be boundedby the Cheeger Inequality [22],√[27], λ21 ≤ η(G) ≤ 2 λ1 , where λ1 is the second smallest
eigenvalue of the graph Laplacian3 of network G. As wewill show in the simulation later, λ21 does not always leadto a tight bound of the extinction time, so next we consider properties that are more accessible for general large
networks.
B. Bounds by Considering Vertex Eccentricity
Recall in Theorem 2, after the hub of a star network is
cured, the extinction time of the virus is bounded by the last
curing event of an infected peripheral vertex, which depends
on the longest time it takes a copy of antidote to pass thoughmultiple hub-peripheral paths of length 1. In a general network
G, if we view every initially cured vertex v ∈ C(0) as a‘hub’, the extinction time also depends on such hub-peripheral
paths, whose lengths are measured in hop-count distancesdist(·, ·). In practice, distance between two vertices is easy
to obtain, and is therefore widely used in various applications,such as routing and influential node detection. Based on thisgraph metric, the eccentricity of a vertex v in network G is
defined as the longest distance of between v and any othervertex in V, that is, G (v) := maxu∈V distG (u, v), and thediameter of network G is defined as the largest eccentricity,
i.e., diam(G) := maxv∈V G (v).
As the first step, consider the case that a single copy ofantidote is distributed to vertex c ∈ V at time 0, i.e. C0 = {c}.
Then propagation time of the antidote to any specific vertex ican be bounded by the following lemma.
3 Let A denote the adjacency matrix of G. The graph Laplacian of G
 − A, where D is the degree sequence
is defined as L(G) = diag(D) is the diagonal matrix with D as its main diagonal.
of G, and diag(D)Since G is undirected and connected, its Laplacian L(G) is symmetric andpositive-semidefinite, and has n non-negative real eigenvalues. Among these,
the second smallest eigenvalue λ1 , referred to as the algebraic connectivity,
measures the expanding property of G. Particularly, the lower bound of η(G)is referred to as the Buser Inequality.

9

Lemma 1: Let Tc,i denote the time that vertex i gets a copyof the antidote originated from vertex c ∈ C0 . We haveE(Tc,i ) ≤dist(c, i)
,
γ

(17)

Proof: Let {Pk }K
k=1 denote the set of paths between vertex
c and i, such that their lengths are in an ascending order, i.e.,lk ≤ lk+1 . For any 1 ≤ k ≤ K, we have
distG (c, i) ≤ l1 ≤ lk ≤ lK .

(18)

Consequently, the curing time Tc,i of vertex i (by the antidote
originated from vertex c) can be re-written ask1≤ Tc,i,
Tc,i = min Tc,i

(19)

1≤k≤K

k
where Tc,iis the attempted curing time of vertex i, by theantidote copy originated from c, and transmitted along pathkis the sum of lk i.i.d. Exponential
Pk . For every k, time Tc,i1kr.v.’s with mean γ , as a result of which r.v. Tc,isatisfieskGamma distribution, i.e., Tc,i ∼ Γ(lk , γ), with mean μk = lγk
and variance σk2 = γlk2 . Then the upper bound in (17) can beobtained through (18) becausekkE(Tc,i ) = E( min Tc,i
) ≤ min E(Tc,i
)=
1≤k≤K

1≤k≤K

l1
,
γ

(20)

where l1 = distG (c, i) is the length of the shortest path
between vertex c and vertex i in graph G.
Lemma 1 provides an upper bound of the expected antidote
dissemination time from a designated vertex c to vertex i,which is also an upper bound of the curing time of vertex i,
if c ∈ C(0). To better facilitate the analysis of the extinction
time, we first provide a technical lemma on the maximum andminimum of multiple Gamma r.v.’s.
Lemma 2: Let Xn = min1≤i≤n Xi be the minimum of nr.v.’s, and Xn = max1≤i≤n Xi be the maximum of them,where each Xi ∼ Γ(ki , θi ), where θi ’s are the rate parameters.
Then E(Xn ) and E(Xn ) are bounded:
1/2
  
n
ki
n − 1  ki
E(Xn ) ≤ max
+
,
(21)
i
θi
n i=1 θi2
1/2
  
n
ki
n − 1  ki.
(22)−
E(Xn ) ≥ mini
θi
n i=1 θi2
When ki = k and θi = θ for every 1 ≤ i ≤ n such that{Xi }i are a set of i.i.d Gamma r.v.’s, tighter bounds exist:
2 ln n,(23)
θ(1 − n−1/k )k ln 2 − ln nE(Xn ) ≥.
(24)
θ
Proof: Equation (21) and (22) follow from [28, Theorem 2.1] and [28, Corollary 2.1] by substituting the mean
μi = E(Xi ) = kθii and variance σi2 = θk2i of Gammai
distributions.
For the i.i.d case, (23) is proved in [29, Eq. (7)]. Now
we prove the lower bound in (24). Let r.v. Yi = −Xi ,then Xn = mini Xi = − maxi Yi  Yn . The moment
generating function (MGF) of r.v. Yi can be derived as
E(Xn ) ≤Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
10

IEEE/ACM TRANSACTIONS ON NETWORKING

Fig. 7. An example of contracting cured set C0 into vertex f (C0 ). In the∗quotient graph GC0 , there is KG/C
= 1 path of length GC (f (C0 )) = 300from f (C0 ) to vertex v7 , and K  = 1.

MY (t) = MX (−t) = (1 + θt )−k , where t < θ as required
by MGF MX (t) of r.v. Xi .
Let set D(M ) = {t ≥ 0|MY (t) ≥ 1}. Then with thetechnique from [29, Eq. (6)], we have1
[ln n + ln MY (t)]inft∈D(M) t1t≤
ln n − k ln(1 + )  g(t),tθE(Yn ) ≤which is true for every t ∈ [0, θ). Notice that g(t) ismonotonically decreasing in [0, θ], so a tighter bound of E(Yn )can be upper derived as g(θ). Then (22) follows from the factthat E(Xn ) = −E(Yn ) ≥ −g(θ).
Based on Lemma 1 and Lemma 2, the extinction timeof the undesired information can be analyzed with graphaugmentation, as illustrated in the following theorem.
Theorem 4: Let G (v) denote the eccentricity of vertex v ingraph G. Let GV (V/V, E  ) denote the resulting graph inducedby contracting vertices in set V ⊂ V to a single vertex f (V ),and removing all multiple edges.4 Given that antidotes are
distributed to the set C0 at time t = 0, The expected extinction
time τe of the virus can be upper bounded by⎧∗
2 ln KG/C
0⎪, if GC0 (f (C0 )) ≤ 10,
⎪
1
−
⎪
G
(f (C0 ))⎪⎨∗C
01−(KG/C )10E(τe ) ≤GC0 (f (C0 )) + (K s − 1)GC0 (f (C0 )),
γ⎪
⎪
⎪
⎪
⎩
in general,(25)∗
where KG/C
is the number of longest shortest paths starting
0
from f (C0 ) in the quotient graph GV (V/V, E  ), and K s ≥∗KG/C+ 1 is the number of shortest paths that start from0f (C0 ), and are longer than GC0 (f (C0 )) − s.
Proof: For an SIC dynamics on graph G, the extinction
time of the virus can be bounded by
max min Tc,i ≤ τe ≤ max min Tc,i .
(26)
i∈I0

c∈C0

i∈V\C0c∈C0First we show when C0 ≥ 2, the extinction time τe on theoriginal graph G is upper bounded by the extinction time τeof the SIC epidemic on the quotient graph GC0 , in which one
unit of antidote is distributed to vertex f (C0 ) at time t = 0.
4 Graph G
V is the quotient graph of G through an equivalence relationshipinduced by partition {V, {v1 }, {v2 }, · · · } where vi ∈ V \ V , so that its
vertex set V/V = (V \ V ) ∪ f (V ) has |V| − |V | + 1 vertices.

Fig. 8. Probability P(X ≤ Y ) for k + s (≤ graph diameter diam(G))
ranging from 5 to 20.

An example of the graph contraction procedure is shownin Fig. 7. Consider vertex v1 , v4 ∈ C0 . Evolution of the
SIC epidemic (spread of virus and antidote) will not beaffected by adding an edge (v1 , v4 ) to G, no matter such edge
(v1 , v4 ) exists in G or not. This is because: i) transmissionof antidotes between any vertex pair is independent withtransmission actions between others; and ii) transmission ofantidote between u and v will not result in any state change.
Since v1 and v4 will stay in cured state forever, we can
combine and contract them into one vertex f ({v1 , v4 }) andkeep all their edges in G, without affecting the evolution
process. The contraction process may result in multiple edges,
by removing which the extinction time may increase. Thenby induction on the contraction of C0 , the extinction timeτe ≤ τe , which is the extinction time of the virus on quotientgraph GC0 .
Therefore, it is sufficient to consider the SIC epidemic ongraph GC0 , with one unit of antidote distributed to f (C0 ) attime t = 0. Then we have the following inequality,τe ≤ τe := max Tf (C0 ),i ≤ max Tf1(C0 ),i ,i∈V\C0i∈V\C0(27)where Tf1(C0 ),i ∼ Γ distGC0 (f (C0 ), i), γ . The last inequalityof (27) follows from (19) in Lemma 1. Next we discussmaxi∈V\C0 Tf1(C0 ),i and the eccentricity GC0 (f (C0 )) of thecentral cured hub f (C0 ).
By definition, distance between any vertex i and the cured
hub f (C0 ) satisfies
distGC0 (f (C0 ), i) ≤ GC0 (f (C0 )) ≤ diam(GC0 ) ≤ diam(G).
(28)
Without loss of generality, suppose GC0 (f (C0 )) = k +s is achieved by the path from f (C0 ) to vertex u in
the quotient graph GC0 . Consider infected vertex i thatis distGC0 (i, f (C0 )) = k hops away from the cured
hub f (C0 ), such that s ≥ 1. Let r.v. X and Y denotethe time it takes a copy of antidote to reach vertex u
and v from the hub f (C0 ), respectively. We first show thatwhen k + s is small, the probability that r.v. X ≤ Y issmall.
Clearly, X ∼ Γ(k + s, θ) and Y ∼ Γ(k, θ), where θ isthe rate parameter, and equals to the curing rate γ in ourXsatisfies Beta distribution withmodel. As a result, r.v. X+Y

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

11

Fig. 9. Bounds and simulation of the extinction time E(τe ) in the general network group of small sizes (n  1000). The curing rate γ in the SF-s scenario
is increased to avoid a lenthy simulation in a sparse graph (with less edges) like SF-s.

TABLE IS TATISTICS OF N ETWORKS U SED IN S IMULATION

parameters k + s and k, andX≤ 0.5)
X +Y 0.5
Γ(2k + s)tk+s−1 (1 − t)k−1 dt,=
Γ(k + s)Γ(k) 0(29)
 ∞ k−1 −xwhere Γ(k) = 0 x
e dx is the Gamma function. It isdifficult to bound (29) due to the integral, so we plot thisprobability for k and s values in Fig. 8, such that k +s reflects
the range of diameter for frequently5 seen networks.
In Fig. 8, the dashed vertical lines identify the diameterdiam(G) of five networks used for simulation validation,
whose statistics are shown in Table I. When k + s ≤diam(G) ≤ 10, the probability that the antidote will reachu sooner than i, who is s-hops closer than u from f (C0 ) issmall (< 0.2) when s ≥ 3. In addition, the rate parameter θ of
the Gamma distribution equals to the curing rate γ, so when
γ is also small, the gap between the two time intervals Y
and X is therefore small as well, such that we only needto consider vertices who are located the furthest from vertex∗
distinct vertices, such as u,f (C0 ) in graph GC0 , i.e., the KG/C
0satisfying distGC0 (f (C0 ), i) = GC0 (f (C0 )). Then the first lineon the right-hand side of (25) follows from the tighter upper∗= 1, the firstbound (23) in Lemma 2. Note that when KG/C
0term is not well-defined, because the denominator equals to 0.
(f (C0 ))G
In this case, we take E(τe ) ≤ C0 γ
instead.
P(X ≤ Y ) = P(

5 In most networks we consider (see Table I for detailed statistics), the network diameter diam(G) = O(log |V|) is small due to the small-world effect,
so probability P(X ≤ Y ) in (29) is also small.

If this condition is not satisfied, e.g., when diam(G) is large,such that P(X ≤ Y ) can not be omitted, we always havethe option to consider more paths, which are possibly shorter,
to upper bound the extinction time. Then the upper bound(second line in (25)) follows from the upper bound for general
distributions, as described in (21) of Lemma 2.
Note that the eccentricity GC0 (f (C0 )) is a property of theaugmented quotient graph GC0 . To apply Theorem 4, we needto know the exact locations (vertices) where copies of antidotes
are disseminated, i.e., set C0 . If such knowledge is not readily
available, the extinction time can still be bounded by the diameter (or more generally, distribution of vertex eccentricities) ofgraph G, as given in the following two corollaries. Proofs ofCorollary 2 and 4 are simple as they directly follow from thefact that GC0 (f (C0 )) ≤ minc∈C0 G (c) ≤ diam(G).
Corollary 2: Particularly when C0 = 1, for any initial
antidote recipient c ∈ V,
E(τe ) ≤1
diam(G) + diam(G)(|Peri(G)|/2 − 1) ,γ
(30)where diam(G) is the diameter of G, and Peri(G) = {v ∈V | (v) = diam(G)} is the set of peripheral vetices in G.
Corollary 2 is also an upper bound of the expected extinction time E(τe ) for the case of C0 > 1, because the more
copies of antidote distributed initially at t = 0, the lesstime it takes to fully remove virus from the network, i.e.,a shorter extinction time. A direct implication of Corollary 2
is that for small-world graphs, which naturally emerges invarious contexts, such as social networks, the extinction time isO( logγ n ), due to the O(log n) scaling of the network diameter.
Though not a tight bound compared to Theorem 3, this corollary is much more accessible, especially for large networks.
Obtaining the eccentricity distribution of a graph, including
diameter and peripheral size, is at most O(n|E|) in timecomplexity with further speedups [30], which is much fasterthan obtaining the Cheeger constant η(G). By the eccentricity
distribution and the initial cured count C0 , a more accurate
upper bound can be derived as follows.
Corollary 3: Suppose vertices in C0 are chosen uniformly
at random from V, and CDF of the eccentricity distribution

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
12

IEEE/ACM TRANSACTIONS ON NETWORKING

Fig. 10.

Bounds and simulation of the extinction time E(τe ) in the general network group of large sizes (n  22000).

of graph G is F (x) (radi(G) ≤ x ≤ diam(G)). The expected
extinction time can be upper bounded by!
"n − C01
E(τe ) ≤−1 ,μC0 + μC0(31)
γdiam(G)diam(G)C0where μC0 =is the expected
k=radi(G) k[1 − F (k)]maximum eccentricity of vertices in the cured set C0 .
Corollary 3 also stems from Theorem 4, by considering the expected maximum eccentricity of the C0 antidote
recipients in C0 , if antidotes are randomly distributed attime 0. Specifically, for any vertex v ∈ V \ C0 , the distance
between i and vertex f (C0 ) in the quotient graph GC0 satisfies distGC0 (f (C0 ), v) ≤ GC0 (f (C0 )) ≤ minc∈C0 G (c) ≤diam(G), which is the diameter of the original graph G.
Changing perspective to the initial infected set I0 , whichcontains all infected vertices at time 0, the expected extinction
time E(τe ) can be bounded below by considering the shortest
paths between vertices in set I0 and set C0 .
Corollary 4: Given the initial infected set I0 = I(t = 0),
the expected extinction time can be lower bounded byE(τe ) ≥1
dist(C0 , i∗ ) ln 2 − lnKi∗ ,γ(32)

where dist(C0 , i) = minc∈C0 {dist(c, i)} denotes theshortest distance between set C0 and vertex i, i∗ =arg max{dist(C0 , i)}, and Ki∗ is the number of shortesti∈I0

paths6 between set C0 and vertex i∗ .
Proof: From (26), we haveτe ≥ max min Tc,i ≥ min Tc,i∗ ,
i∈I0

c∈C0

c∈C0

(33)

k
where Tc,i∗ = min1≤k≤Ki∗ Tc,i
∗ is the minimum of Ki∗
ki.i.d. Gamma r.v.’s, and each Tc,i∗ ∼ (dist(C0 , i), γ1 ), whichcomes from Lemma 1. Then the lower bound in (32) follows
immediately from (24) in Lemma 2.
6 In practice, obtaining quantity K ∗ requires executing path searchesirepetitively. To avoid high computation load in the simulation, we use theupper bound of Ki∗ , that is, |{i ∈ I0 |dist(C0 , i) = dist(C0 , i∗ )}| whenevaluating the lower bound in Corollary 4.

C. Validation in Synthetic and Real-World Networks
To validate the derived bounds, especially the extinction
time of the undesired information, we test the derived bounds
in five networks of three different topologies: the Erdös-Rényi(random graph) topology, including ER-s (edge connecting
probability p = 7.50 × 10−3 ) and ER-l (p = 6.76 × 10−4 );the scale-free topology, including SF-s (generated with the
Barabási–Albert model); and real world fractions of Facebook,
FB-s (Dataset No. 107 from [31]) and FB-l7 (webgraphfrom [32]). Their statistics are presented in Table I, in which
the networks are grouped into two sets, as indicated by the‘-s’ (size n  1000) and ‘-l’ (size n  22000) suffixes.
In Fig. 9 and Fig. 10, the simulated extinction time areshown in grey dots, whose mean E(τe ) is identified by blue
‘×’ markers. Each instance along the x-axis corresponds to thesame initial cured set C0 and infected set I0 , which is realized
100 times to obtain E(τe ). The red round markers and blacksquares markers correspond to the upper bounds in Theorem 4
and Corollary 4, respectively, both of which are determined byvertex eccentricities. The red dashed line and green lines withtriangle markers correspond to the upper bounds presented
in Corollary 2 that relies on network diameter diam(G), andTheorem 3 that relies on the Cheeger constant,8 respectively.
We highlight the following observations:
1) Topological Properties: The small diameter diam(G) andthe relatively large algebraic connectivity λ1 of the randomgraph topology (ER-s, ER-l) indicate that they are much
more ‘regular’ than SF-s, FB-s, and FB-l, in the sense thatvertices differ less in degree, centrality, etc. (indicating different importance/influential in status of individuals). As aresult, the expected extinction time E(τe ) varies less violently
in Fig. 9(a), Fig. 10(a), and Fig. 10(b).
7 The actual FB-l network used in simulation has 238 less vertices than theoriginal dataset, as can be seen from Table I, because isolated vertices are
removed to avoid the case of infinite extinction time (τe = ∞).
8 Approximating the Cheeger constant η(G) with the lower bound λ1 results
2
in a very loose bound of E(τe ) in smaller networks and FB-l, so the upperbound (solid green line) is not shown in Fig. 9 or Fig.10(c). The dashedgreen√ lines correspond to the upper bound in Cheeger’s Inequality η(G) ≤2 λ1 , which are presented to make a comparison with bounds based on
eccentricities, hence the star sign in the legend.

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
WANG et al.: MODELING AND ANALYSIS OF CONFLICTING INFORMATION PROPAGATION IN A FINITE TIME HORIZON

13

strategy on a portion of Facebook with 324 vertices, as illustrated in Fig. 11. Compare it with the distribution strategy
based on degree (dotted blue line with triangle markers),
adopting the betweenness centrality metric (solid red line withround markers) as guideline can drastically reduce both theextinction time and the half-life time, which indicates that theundesired information is effectively controlled (shorter halflife) and quickly exterminated (shorter extinction time).
V. C ONCLUSION
Fig. 11. Effectiveness of antidote distribution strategies based on betweenness
centrality and vertex degree (I0 = 150).

Despite differences in average degree d¯ and algebraic connectivity λ1 , the similarity in vertex eccentricity properties(diameter and radius) between ER-s and and FB-s leads to thesame range of extinction time in Fig. 9(a) and Fig. 9(c), whichindicates the usefulness of Corollary 2 and Corollary 4.
Due to the relatively large diameter diam(G) of SF-s and
FB-l, the probability in (29) can not be neglected, so the first
condition of (25)) in Theorem 4 does not hold. However,the second condition still holds, and leads to tight bounds (redround markers) in Fig. 9(b) and Fig. 10(c).
2) Tightness of the Bounds: Corollary 2 (dashed red lines)that relies only on network diameter diam(G) is an easyto-obtain, but not tight upper bound. Theorem 4 (round redmarkers) and Corollary 4 (black square markers) are tighter inthe less ‘regular’ SF-s, FB-s, and FB-l, due to the existenceof few ‘dominant’ longest shortest paths, i.e., K ∗ is small.
In contrast, for the ER-s and ER-l newtork, vertex degrees
and pair-wise distances are highly homogeneous (small variance in degree distribution), resulting in a large K ∗ that
affects the tightness of both the upper and lower bounds by
eccentricities. This is especially true when the initial cured
count C0 is large, e.g., in Fig. 10(a). In this case, further upperbounding Theorem 3 by setting η(G) = λ21 (solid green lines
with triangle markers) proves to be a tighter bound.
However, Theorem 3 that relies on the Cheeger constantη(G), or more accurately, the algebraic connectivity λ1 ,becomes less effective than Theorem 4, when the initial cured
count C0 decreases, as shown in Fig. 10(b). This effect is more
obvious in smaller networks√ (Fig. 9), where even the maximum
possible value η(G) = 2 λ1 of the Cheeger Constant (dottedgreen lines) are not tight, especially in SF-s and FB-s.
D. Implication on Antidote Distribution
From the proof of Theorem 4, another implication is that,the extinction time of the undesired information can bebounded by the number and the length of shortest paths,
which go through vertices of the initial cured set C0 . Thisobservation sheds light on antidote distribution (injectionof desired information), when used as a counter-measureagainst the epidemic spreading of undesired information.
A general guideline on selecting vertices for set C0 is tochoose vertices that sit on the most number of shortest paths,
i.e., vertices with high betweenness centrality. We test thisIn this paper, we studied conflicting information propagationin networks. Motivated by examples in social networks, computer networks, and IoT, we introduced a Susceptible-InfectedCured epidemic model, to capture the transient competition
between the desired and undesired information. Our modelallowed us to examine the impact of network topology, propagation intensity, and the initial condition on the propagation
processes of both pieces of information, such that short-term
behaviors of the dynamics, namely, the lifetime of the undesired information can be characterized.
Our analysis, validated by simulation in network of various
topologies, provided insights on the transient evolution of suchnetwork dynamics. For instance, the derived bounds revealed
the level of ‘bottleneckness’ in a network may lead to different,
even contrasting scaling behavior of information’s lifetime,with respect to the size of a network. Our findings on theimpact of network topology and initial condition permitted
the estimation of information lifetime before the dynamics
unfolds, and can guide information distributor to efficiently
allocate the limited resource to minimize the the impact of
the undesired information on individuals. For example, a computer network operator who aims to effectively exterminate a
spreading virus by distributing security patches, may first give
patches to computers that locate on the most shortest paths,
instead of computers with the most connections.
There are several directions that can be explored to further
our understanding on the network dynamics of conflicting
information propagation: The virus-antidote model can begeneralized to allow semi-conflicting information pairs, suchthat the more complex competition between half-rumor andhalf-truth can be examined. The analysis can be extended toinclude multiple epochs of short-term competition, such thatthe best time to inject conflicting information can be studied.
In addition, the decay of propagation intensity (popularity
of information) over time can also be introduced to moreaccurately investigate this transient dynamics in finer temporalgrains. We hope that our model and findings contribute to theknowledge of information propagation, and they serve as thefoundation and motivation for future research in this direction.
R EFERENCES[1] J. Wiener and N. Bronson. (Oct. 2014). Facebook’s Top Open Data
Problems. [Online]. Available: https://research.fb.com/facebook-s-topopen-data-problems/[2] Cisco Visual Networking Index: Global Mobile Data Traffic Forecast
Update, 2017–2022, Cisco, San Jose, CA, USA, Feb. 2019.
[3] H. Alexander. (2013). Boston Bomb: Reddit Apologises for Identifying Wrong Suspects. [Online]. Available: http://www.telegraph.
co.uk/news/worldnews/northamerica/usa/10012382/

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
14[4] D. Lee. (2013). Boston Bombing: How Internet Detectives Got it
Very Wrong. [Online]. Available: http://www.bbc.com/news/technology22214511[5] M. Garnaeva, V. Chebyshev, D. Makrushin, R. Unuchek, and A. Ivanov.
(2014). Kaspersky Security Bulletin 2014. Overall Statistics for 2014.
[Online]. Available: http://securelist.com/analysis/kaspersky-securitybulletin/68010/kaspersky-security-bulletin-2014-overall-statistics-for2014/[6] J. Milliken, V. Selis, and A. Marshall, “Detection and analysis of thechameleon WiFi access point virus,” EURASIP J. Inf. Secur., vol. 2013,
no. 1, p. 2, Oct. 2013.
[7] R. Pastor-Satorras and A. Vespignani, “Epidemic spreading in scale-free
networks,” Phys. Rev. Lett., vol. 86, no. 14, pp. 3200–3203, Apr. 2001.
[8] J.-W. Wang and L.-L. Rong, “Cascade-based attack vulnerability on the
US power grid,” Saf. Sci., vol. 47, no. 10, pp. 1332–1336, Dec. 2009.
[9] D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos,“Epidemic thresholds in real networks,” ACM Trans. Inf. Syst. Secur.,vol. 10, no. 4, pp. 1:1–1:26, Jan. 2008.
[10] B. A. Prakash, D. Chakrabarti, N. C. Valler, M. Faloutsos, andC. Faloutsos, “Threshold conditions for arbitrary cascade models on
arbitrary networks,” Knowl. Inf. Syst., vol. 33, no. 3, pp. 549–575,
Jul. 2012.
[11] A. Ganesh, L. Massoulie, and D. Towsley, “The effect of network
topology on the spread of epidemics,” in Proc. 24th Annu. Joint
Conf. IEEE Comput. Commun. Soc. (INFOCOM), vol. 2, Mar. 2005,
pp. 1455–1466.
[12] M. Lelarge, “Efficient control of epidemics over random networks,”
in Proc. 11th Int. Joint Conf. Meas. Modeling Comput. Syst.
(SIGMETRICS), New York, NY, USA, 2009, pp. 1–12.
[13] S. Krishnasamy, S. Banerjee, and S. Shakkottai, “The behavior of
epidemics under bounded susceptibility,” in Proc. ACM Int. Conf. Meas.
Modeling Comput. Syst. (SIGMETRICS), New York, NY, USA, 2014,
pp. 263–275.
[14] B. A. Prakash, H. Tong, N. Valler, M. Faloutsos, and C. Faloutsos, “Virus
propagation on time-varying networks: Theory and immunization algorithms,” in Proc. Eur. Conf. Mach. Learn. Knowl. Discovery Databases(ECML PKDD). Berlin, Germany: Springer-Verlag, 2010, pp. 99–114.
[15] C. Nowzari, V. M. Preciado, and G. J. Pappas, “Analysis and control of epidemics: A survey of spreading processes on complex
networks,” 2015, arXiv:1505.00768. [Online]. Available: http://arxiv.
org/abs/1505.00768[16] Y. Lin, J. C. S. Lui, K. Jung, and S. Lim, “Modeling multi-state
diffusion process in complex networks: Theory and applications,” inProc. Int. Conf. Signal-Image Technol. Internet-Based Syst., Dec. 2013,
pp. 506–513.
[17] B. A. Prakash, A. Beutel, R. Rosenfeld, and C. Faloutsos, “Winnertakes all: Competing viruses or ideas on fair-play networks,” in Proc.
21st Int. Conf. World Wide Web (WWW), New York, NY, USA, 2012,
pp. 1037–1046.
[18] A. Dadlani, M. S. Kumar, M. G. Maddi, and K. Kim, “Mean-field
dynamics of inter-switching memes competing over multiplex social
networks,” IEEE Commun. Lett., vol. 21, no. 5, pp. 967–970, May 2017.
[19] M. E. J. Newman, “Threshold effects for two pathogens spreading on a
network,” Phys. Rev. Lett., vol. 95, no. 10, Sep. 2005, Art. no. 108701.
[20] M.-C. De Marneffe, A. N. Rafferty, and C. D. Manning, “Finding
contradictions in text,” in Proc. ACL, vol. 8, 2008, pp. 1039–1047.
[21] A. Beutel, B. A. Prakash, R. Rosenfeld, and C. Faloutsos, “Interacting
viruses in networks: Can both survive?” in Proc. 18th ACM SIGKDD
Int. Conf. Knowl. Discovery Data Mining (KDD), New York, NY, USA,2012, pp. 426–434.
[22] S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and theirapplications,” Bull. Amer. Math. Soc., vol. 43, no. 4, pp. 439–562,
Aug. 2006.
[23] H. Zhang, Z. Zhang, and H. Dai, “Gossip-based information spreading
in mobile networks,” IEEE Trans. Wireless Commun., vol. 12, no. 11,
pp. 5918–5928, Nov. 2013.
[24] F. Qi and B.-N. Guo, “Sharp bounds for harmonic numbers,” 2010,arXiv:1002.3856. [Online]. Available: http://arxiv.org/abs/1002.3856[25] J. Yang and J. Leskovec, “Patterns of temporal variation in online
media,” in Proc. 4th ACM Int. Conf. Web Search Data Mining (WSDM),
New York, NY, USA, 2011, pp. 177–186.

IEEE/ACM TRANSACTIONS ON NETWORKING[26] A. Louis, “The complexity of expansion problems,” Ph.D. dissertation,
Georgia Inst. Technol., Atlanta, GA, USA, 2014.
[27] F. R. Chung, “Laplacians of graphs and Cheeger’s inequalities,” Combinatorics, Paul Erdos Eighty, vol. 2, nos. 157–172, pp. 2–13, 1996.
[28] T. Aven, “Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables,” J. Appl. Probab., vol. 22, no. 3,
pp. 723–728, 1985.
[29] G. Dasarathy. (2011). A Simple Probability Trick for Bounding the
Expected Maximum of N Random Variables. [Online]. Available:
https://www.ece.rice.edu/∼gd14/files/maxGaussians.pdf[30] F. Takes and W. Kosters, “Computing the eccentricity distribution oflarge graphs,” Algorithms, vol. 6, no. 1, pp. 100–118, Feb. 2013.
[31] J. Leskovec and J. J. Mcauley, “Learning to discover social circles in
ego networks,” in Advances in Neural Information Processing Systems,
P. Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, Eds.
2012, pp. 548–556.
[32] B. Rozemberczki, C. Allen, and R. Sarkar, “Multi-scale attributed
node embedding,” 2019. [Online]. Available: https://snap.stanford.edu/
data/facebook-large-page-page-network.html

Jie Wang (Student Member, IEEE) received the
Ph.D. degree in computer engineering from North
Carolina State University, Raleigh, NC, USA,in 2019. She is currently a Post-Doctoral Research
Scholar with the Department of Electrical and Computer Engineering, North Carolina State University.
Her research interests lie in the area of networking,including modeling and performance evaluationof networked systems, such as the Internet-ofThings, cyber-physical systems, and social networks,
dynamic spectrum access, mobile/edge computing,and mobile big data.

Wenye Wang (Fellow, IEEE) received the M.S.E.E.
and Ph.D. degrees in computer engineering from theGeorgia Institute of Technology, Atlanta, GA, USA,in 1999 and 2002, respectively. She is currently
a Professor with the Department of Electrical andComputer Engineering, North Carolina State University, Raleigh, NC, USA. Her research interests
include mobile and secure computing, modeling andanalysis of wireless networks, network topology,
and architecture design. She has been a memberof the Association for Computing Machinery since1998 and a member of the Eta Kappa Nu and Gamma Beta Phi honorarysocieties since 2001. She was the recipient of the NSF CAREER Award
2006. She was a corecipient of the 2006 IEEE GLOBECOM Best Student
Paper Award–Communication Networks–and the 2004 IEEE Conference on
Computer Communications and Networks Best Student Paper Award.

Cliff Wang (Fellow, IEEE) received the Ph.D.
degree in computer engineering from North Carolina
State University in 1996. He currently serves as theComputing Sciences Division Chief of the Army
Research Office. He is also appointed as an AdjunctFaculty Member of computer science with the College of Engineering, North Carolina State University.
He has been carrying out research in the areasof computer vision, medical imaging, high speed
networks, and most recently information security.

Authorized licensed use limited to: N.C. State University Libraries - Acquisitions & Discovery S. Downloaded on March 27,2020 at 11:30:09 UTC from IEEE Xplore. Restrictions apply.