Seeking powerful information initial spreaders in online social networks: a dense group perspective

Abstract

The rapid growth of online social networks (OSNs) has ultimately facilitated information spreading and changed the economics of mobile networks. It is important to understand how to spread information as widely as possible. In this paper, we aim to seek powerful information initial spreaders with an efficient manner. We use the mean-field theory to characterize the process of information spreading based on the Susceptible Infected (SI) model and validate that the prevalence of information depends on the network density. Inspired by this result, we seek the initial spreaders from closely integrated groups of nodes, i.e., dense groups (DGs). In OSNs, DGs distribute dispersedly over the network, so our approach can be fulfilled in a distributed way by seeking the spreaders in each DG. We first design a DG Generating Algorithm to detect DGs, where nodes within the DG have more internal connections than external ones. Second, based on the detected DGs, we design a criterion to seek powerful initial spreaders from each DG. We conduct experiments as well as statistical analysis on real OSNs. The results show that our approach provides a satisfactory performance as well as computational efficiency.

Appendix: Notations

G :

the graph

${\mathcal {V}}$, ${\mathcal {E}}$ :

the set of nodes and links

$v_i$ :

a node belongs to ${\mathcal {V}}$

${\mathbf {A}}$ :

the adjacency matrix of graph G

$A_{i,j}$ :

an element of ${\mathbf {A}}$

$\alpha$ :

the probability that a node is infected by one of its neighbor

$P(v_i,t)$ :

the probability that $v_i$ is infected by its infected neighbors at time t

I(t):

the number of infected nodes in G at time t

i(t):

the density of infected nodes in G at time t

N :

the total number of nodes in G

$n_I (t)$ :

the average number of infected neighbors of an uninfected node

k :

the degree of a node

$k_i$ :

the degree of node $v_i$

$\left\langle k \right\rangle$ :

the average degree

$\tau$ :

the time constant for information spreading in graph G

$I_k(t)$ :

the number of infected nodes at time t which have the same degree k

$i_k(t)$ :

the density of infected nodes at time t which have the same degree k

$N_k$ :

the number of nodes with degree k

$P_k$ :

the probability that a nodes’ degree equals to k

$i_k^*(t)$ :

the density of infected neighbors of the k-degree node at time t

$i^*(t)$ :

the density of infected neighbors of the node at time t

${\mathcal {D}}$ :

a set of nodes or a dense group

${\varPhi }({\mathcal {D}})$ :

a metric for ${\mathcal {D}}$, the density of ${\mathcal {D}}$

$\left| {\mathcal {D}}_l \right|$ :

the number of links in ${\mathcal {D}}$

$\left| {\mathcal {D}} \right|$ :

the number of nodes in ${\mathcal {D}}$

${\mathcal {D}}_{ca}$, ${\mathcal {D}}^i$ :

a candidate set of nodes or a candidate cluster

$\tau ({\mathcal {D}})$ :

the threshold of determining ${\mathcal {D}}_{ca}$

${\mathcal {D}}^{max}$ :

the cluster who has the largest density

$N_E$ :

the number of edges of an n-node complete graph

$d({\mathcal {D}})$ :

the difference between $N_E$ and $\left| {\mathcal {D}} \right|$

$D({\mathcal {D}})$ :

the upper bound of the number of absent links for a cluster

$\pi$ :

the probability that node $v_i$ is infected by its neighbors in a time slot

N(i):

neighbors of node $v_i$

$p_{j,t-1}$ :

the probability that $v_j$ has been infected before time slot t

${\mathbf {I}}$ :

the identity matrix

${\mathbf {P}}_t$ :

a vector that concludes the infected probability of each node at time t

$I_t$ :

the number of infected nodes at time t; same with I(t)

${\mathbf {e}}$ :

the identity vector

$l_i$ :

the number of physical outward link of the node

${\mathbf {L}}$ :

a square matrix $diag(l_1,l_2,\ldots ,l_n)$

$L_t$ :

the number of DA links at time t

$n_s$ :

the number of initial information spreaders to be sought

$S_k$ :

the sought node

${\mathcal {N}}_S$ :

the set of sought nodes

${\mathcal {D}}_{ol}$ :

the set of nodes in the overlapping area

${\mathcal {N}}^{ol}$ :

the set of sought nodes from overlapping DGs

${\mathcal {D}}_{in}$ :

an integrity composed by multiple clusters

B(t):

the benefit or the number of DA links at time t

$B_0 (t)$ :

the optimal benefit

${\mathcal {N}}_1^*$ :

the optimal sets of spreaders from ${\mathcal {D}}_1$ using the approach in Section 6.2

$B_{ol}(t)$ :

the benefit when using the approach in 6.3 to seek spreaders in overlapping DGs.

$C(n_s)$ :

the cost of informing the initial spreaders

$\beta$ :

a parameter that adjusts adjust the two terms with the same unit in Eq. (27)

GOS :

the sought node by GeneralGreedy

LOS :

the sought node from DG

R :

simulation round

M :

the number of G’s links

${\mathcal {N}}$ :

neighbors that are not belong to the DGs

${\mathcal {S}}_f$ :

single node’s messages reception frequency

${\mathcal {A}}_f$ :

collection’s average messages reception frequency