A heat diffusion model based algorithm for personalized influence maximization in social network

Abstract

Nowadays personalized influence maximization has become a new branch of influence maximization in social network. The existed methods mainly focus on independent cascade model and linear threshold model, in those two models, nodes’ influence forecast depends on the Monte-Carlo simulation. In order to simulate the propagation of influence more efficiently, we introduce heat diffusion model to the study of personalized influence maximization in this paper. The diffusion process of heat is adopted to simulate the influence of information among users. Furthermore, we propose a target’s heat greedy algorithm based on the analysis of the laws of the heat propagation. Experimental results on real datasets show that our proposed algorithm is effective.

Keywords

Social network personalization influence maximization heat diffusion model

1. Introduction

Since 2001, the influence maximization (IM) problem in social network has been widely studied [6,11]. Both the range of influence spread and the efficiency of algorithms have been greatly improved [1,2,7,10,12,14]. However, these methods which treat each network user equally fail to satisfy the demands in reality.

Personalized influence maximization [9] is a branch of influence maximization. Due to the long-term marketing and media experiences, enterprises or media services have accumulated some important users. These users are expected to produce far greater values than that of ordinary users. However owing to budget limits, enterprises or media are unable to spread the influence to all friends of the important users at the initial stage. The purpose of personalized influence maximization is to find a set of initial users (referred as seeds) of size k which can maximally influence a specific user (referred as target node). Currently, the social data analysis company as Klout, PeerIndex is using influence maximization algorithm for Marketing consulting [15]. With the development of personal values in business marketing, seeking effective personalized influence maximization algorithm should be the new requirements of social data researcher. To address the issue, we propose a heat diffusion model based algorithm. The results obtained by conducting the experiments on different datasets validate the effectiveness of the proposed algorithm.

The rest of the paper is organized as follows. Section 2 briefly reviews the related works. Section 3 describes the propagation mechanism of heat diffusion model (HDM). Section 4 gives a greedy algorithm based on investigating the propagation characteristics of HDM. Section 5 presents the experiments and analyses. Section 6 draws a conclusion.

2. Related works

Since the personalized influence maximization was raised in 2013, various algorithms including Random, LND, local greedy algorithm (LGA) and the optimization methods have been proposed [8,9,15]. LND and Random do not couple with influence propagation models. Their problem solving strategies are simple and cannot guarantee the desired solution. Guo et al. [9] put forward LGA based on independent cascade model. It could forecast the influence from nodes to the target by conducting Monte-Carlo simulation on each edge of network. For the sake of improve efficiency, they proposed an efficient local greedy algorithm (ELGA) which takes the whole network as the Monte-Carlo simulation object, instead of each edge of the network. By doing so, the times of performing Monte-Carlo simulation can be greatly reduced. However, ELGA is still time consuming compared to LND and Random. For example, ELGA takes $10^{6}$ seconds on a directed graph with 602 nodes and 17595 edges. Zhang et al. [16] took multiple nodes as target and adopt K-medoids clustering to realize more reliable information coverage on target user community. In addition, a different solution based on linear threshold model considering the cumulative effect of information influence has been proposed in the literature [8]. It is noted that approaches based on linear threshold model or independent cascade model approximately evaluate the influenced strength of target node through Monte-Carlo simulation. In order to make the simulation results closer to the reality, the times of Monte-Carlo simulation has to be increased, and it will definitely reduce the efficiency.

In [13], Ma et al. proposed a social network marketing model named heat diffusion model that applies heat diffusion theory from physics to describe the diffusion of influence in social network. HDM is applicable to undirected graph, directed graph, and directed graph containing prior knowledge. In their studies, the influence propagation is not simulated by Monte-Carlo simulations. Furthermore, Doo et al. [4,5] extended the HDM of directed graph to make node’s heat flow to other adjacent nodes with a probability. By using HDM, the range and strength of influence propagation can be obtained with a simulation, and influenced strength on target node can be computed at different time. Based on the HDM, Chen et al. [3] proposed an algorithm called CIM to solve the classic influence maximization. However, the HDM based personalized influence maximization remains unresolved. In this paper, we present target’s heat greedy algorithm to solve the problem.

3. HDM based influence propagation

It is a natural physical phenomenon that heats flows to the low temperature position from a high temperature position in medium. The influence propagation among users in a social network likes heat propagation in a physical medium. The influence propagation tends to transfer information to the one who have yet been influenced, and highly influenced users are prone to propagate information to marginally influenced ones. Therefore, heat diffusion model is applied to simulate the influence spread in social network.

In existed studies, a social network is treated as a directed graph and denoted by $G (V, E)$ , where the node set V represents the set of all users in a network, and the edge set E is a set of the relationships among all users and an edge serves as a channel for diffusing “heat” among nodes.

The heat received by a node $v_{i}$ represents the sources from $v_{i}$ ’s precursor neighbor set $N^{+} (v_{i})$ , and it is propagated to nodes in the set of $v_{i}$ ’s succeeding neighbors $N^{-} (v_{i})$ . At the initial time $t_{0}$ , the heat gathering on $v_{i}$ is marked as $h_{i} (0)$ . The heat on $v_{i}$ is marked as $h_{i} (t)$ when time goes to t. $h (t)$ is used to denote a $n \times 1$ vector consisting of the heat values of all nodes in a network at time t, where n represents the number of nodes in $G (V, E)$ : $\begin{matrix} (1) & h (t) = {[h_{1} (t), h_{2} (t), h_{3} (t), \dots, h_{i} (t), \dots, h_{n} (t)]}^{T} \end{matrix}$

$h (t)$ is jointly affected by the vector of the initial distribution of heat $h (0)$ , thermal conductivity a, the time t of influence propagation, and the connecting relationships among nodes [13]: $\begin{matrix} (2) & \begin{matrix} h (t) & = e^{α \cdot t \cdot H} \cdot h (0) \\ = (I + α \cdot t \cdot H + \frac{α^{2} \cdot t^{2}}{2!} H^{2} + \frac{α^{3} \cdot t^{3}}{3!} H^{3} + \dots) \cdot h (0) \end{matrix} \end{matrix}$ where e is the Euler number, H is a n-order matrix: $\begin{matrix} (3) & H_{i j} = \{\begin{matrix} 1 / d_{j}, & \exists e_{v_{j}, v_{i}} \in E \\ - 1, & i = j and d_{i} > 0 \\ 0, & otherwise \end{matrix} \end{matrix}$

For example, given a network in Fig. 1, supposing that $a = 0.15$ and the initial heat of node $v_{2}$ is 10, the variation process of the accumulated heats in each node with t change from 0 to 10 is presented as follows.

Fig. 1.

Topological graph.

At time 0, we obtain: $\begin{matrix} (4) & h (0) = {[0, 10, 0, 0, 0, 0, 0]}^{T} \end{matrix}$

According to equation (3), different elements in the main diagonal of the matrix H, such as $H_{22}$ , are all valued as $- 1$ . By deducing, H can be obtained as: $\begin{matrix} (5) & H = (\begin{matrix} - 1 & 0 & 1 / 2 & 0 & 0 & 0 & 0 \\ 1 & - 1 & 0 & 0 & 1 / 2 & 0 & 0 \\ 0 & 1 / 2 & - 1 & 1 / 3 & 0 & 0 & 0 \\ 0 & 1 / 2 & 0 & - 1 & 1 / 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & - 1 & 0 & 1 \\ 0 & 0 & 1 / 2 & 1 / 3 & 0 & - 1 & 0 \\ 0 & 0 & 0 & 1 / 3 & 0 & 1 & - 1 \end{matrix}) \end{matrix}$

On the basis of equation (2), the heat of each node is computed and shown in Fig. 2.

Fig. 2.

Heat diffusion.

Take node $v_{2}$ in Fig. 1 for example, there are two edges which taking $v_{2}$ as the source, so $d_{2}$ is 2. The terminals of the edges are $v_{3}$ and $v_{4}$ , respectively, so both $H_{32}$ and $H_{42}$ are $1 / 2$ . The elements of the second column in H are valued as 0 except for $H_{32}$ , $H_{42}$ , $H_{22}$ . From Fig. 2, we can see that the heat gradually flows from $v_{2}$ to other nodes as time goes on. In the simulation of the social network influence propagation, the heat of nodes is seen as the influenced strength of the nodes.

4. The HDM based personalized influence maximization algorithm

The HDM based personalized influence maximization problem is defined as follows:

Given a target user $v_{x}$ and a deadline t, find the most influential set S containing k nodes in V. That means the influenced strength of $v_{x}$ exerted by S is maximal. It is formally described as: $\begin{matrix} (6) & S = arg max_{S_{i} \subseteq V ∖ v_{x}, | S_{i} | ⩽ k} σ_{t} (S_{i}) \end{matrix}$ where $S_{i}$ denotes a set consisting of k random nodes in V and $σ_{t} (S_{i})$ denotes the influenced strength on $v_{x}$ at time t after endowing initial influence on $S_{i}$ .

4.1. The analysis of the issues on personalized influence maximization

On the basis of the definition, we know that the issue to be solved lies in $σ_{t} (S_{i})$ when t is given. However, according to combinatorial mathematics, there are $C_{n - 1}^{k}$ cases for $S_{i}$ which meets the conditions. If all these cases are computed and sorted by using an exhaustive method, it will consume a large amount of time.

By analyzing HDM and using the left distributive law of matrix multiplication, the equation (2) is decomposed as follows: $\begin{matrix} (7) & \begin{matrix} h (t) & = e^{α \cdot t \cdot H} \cdot h (0) \\ = e^{α \cdot t \cdot H} \cdot {[h_{1} (0), h_{2} (0), h_{3} (0), \dots, h_{i} (t), \dots, h_{n} (0)]}^{T} \\ = e^{α \cdot t \cdot H} \cdot [\begin{matrix} h_{1} (0) \\ 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}] + \dots + e^{α \cdot t \cdot H} \cdot [\begin{matrix} 0 \\ ⋮ \\ h_{i} (0) \\ ⋮ \\ 0 \end{matrix}] + \dots + e^{α \cdot t \cdot H} \cdot [\begin{matrix} 0 \\ ⋮ \\ 0 \\ 0 \\ h_{n} (0) \end{matrix}] \end{matrix} \end{matrix}$ where $h (t)$ is the superposition of propagation effects under the initial influence $h_{i} (0)$ for each $v_{i} \in V$ . Let $σ_{t} (v_{i})$ represents the influenced strength on $v_{x}$ by $v_{i}$ at t. When $v_{i}$ is endowed with initial influence, $σ_{t} (v_{i})$ is calculated as $h_{x} (t)$ which is a value corresponding to $v_{x}$ in $h (t)$ $\begin{matrix} (8) & σ_{t} (v_{i}) = h_{x} (t) \end{matrix}$

Only the nodes in $S_{i}$ are endowed with initial influence when computing $σ_{t} (S_{i})$ , initial influenced strength of the node which does not belong to $S_{i}$ is 0, and $h_{x} (0)$ is 0 as well. Hence, $σ_{t} (S_{i})$ can be obtained by merely assigning initial influence to each node in $S_{i}$ and simulating heat diffusion on $G (V, E)$ . $\begin{matrix} (9) & σ_{t} (S_{i}) = \sum_{v_{i} \in S_{i}} σ_{t} (v_{i}) \end{matrix}$

4.2. Target’s heat greedy algorithm

Based on the law of influence propagation and the definition of $σ_{t} (S_{i})$ , target’s heat greedy algorithm (THGA) is proposed. The detailed pseudo codes are described as Algorithm 1 .

Algorithm 1

THGA

This algorithm firstly initializes the seed set S (line. 1). To collect the influence reaching the target node $v_{x}$ more precisely, the algorithm removes the edges that taking $v_{x}$ as source when simulating heat diffusion. As a result, the graph $G^{*} (V, E^{*})$ is generated (line. 2). By doing this, the statistics omission of the influences due to the spread from $v_{x}$ to other nodes can be avoided. Afterwards, each non-target node $v_{i}$ is processed as follows: $h (0)$ is set to 0, $h_{i} (0)$ is set to an initial influence value of $Q_{0}$ . And then by simulating the heat diffusion process on $G^{*} (V, E^{*})$ , $σ_{t} (v_{i})$ is computed (line. 3∼7). Furthermore, all non-target nodes’ $σ_{t} (v_{i})$ are sorted into a sequence, and the k nodes in front of the sequence are used to generate the seed set (line. 8∼10). $Q_{0}$ denotes a non-zero parameter which is set for solving $σ_{t} (v_{i})$ . On the premise of the consistency of the initial influence values for all nodes, the value of $Q_{0}$ has no influence on the sequenced results of $σ_{t} (v_{i})$ , therefore it does not change the results for the selection of seeds.

In order to better understand the algorithm, the $v_{6}$ in Fig. 1 is taken as target node to describe the process of THGA. At first, the edges taking $v_{6}$ as the source are removed, as is shown in Fig. 3.

Fig. 3.

The graph after removing the edges that taking $v_{6}$ as source.

H of this graph is presented as $\begin{matrix} (10) & H = (\begin{matrix} - 1 & 0 & 1 / 2 & 0 & 0 & 0 & 0 \\ 1 & - 1 & 0 & 0 & 1 / 2 & 0 & 0 \\ 0 & 1 / 2 & - 1 & 1 / 3 & 0 & 0 & 0 \\ 0 & 1 / 2 & 0 & - 1 & 1 / 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & - 1 & 0 & 1 \\ 0 & 0 & 1 / 2 & 1 / 3 & 0 & - 1 & 0 \\ 0 & 0 & 0 & 1 / 3 & 0 & 0 & - 1 \end{matrix}) \end{matrix}$

Table 1

The influenced strength from $v_{i}$ to $v_{6}$

$v_{i}$	$σ_{10} (v_{i})$
$v_{1}$	0.2881
$v_{2}$	0.6351
$v_{3}$	0.9121
$v_{4}$	0.8274
$v_{5}$	0.4298
$v_{7}$	0.1687

Assuming $Q_{0}$ is 5, $a = 0.15$ and $t = 10$ , Table 1 lists the influenced strength of $v_{6}$ from each node $v_{i}$ .

Given $k = 2$ . According to equation (6), $σ_{10} (v_{i})$ will be sequenced in a decreasing order. Then, we take top k nodes in the sequence as the seeds, that is $v_{3}$ and $v_{4}$ .

5. Experiments and analysis

In order to assess the performance of THGA, k-step [13], LND and Random are selected as reference algorithms. The k-step is similar to THGA, which also employs the greedy strategy based on HDM. However, they are different: k-step aims to solve the classic influence maximization problems. The reason we select k-step as reference is to explore the influenced strength of target node exerted by classic influence maximization seed set. Also, we compare the time consumed by k-step and THGA. The programming language C++ is used to code THGA described in Section 4. The computer on which the code is executed has an Intel Xeon E5-1620 v2 3.70 GHZ processor and a 16 GB memory.

In order to verify the reliability of the experimental results, three social network datasets with different statistic characteristics are selected as test data. All of test data can be gotten from Stanford Network Analysis Platform (http://snap.stanford.edu/index.html). The data sources and their statistic characteristics are listed in Table 2.

Table 2
The test datasets

Dataset 1 Dataset 2 Dataset 3

Name Gnutella08 wiki-Vote Epinions1

Source P2P network Wikipedia vote Epinions.com

Number of nodes 6301 7115 75879

Number of edges 20777 103689 508837

Average cluster coefficient 0.0109 0.1409 0.1378

	Dataset 1	Dataset 2	Dataset 3
Name	Gnutella08	wiki-Vote	Epinions1
Source	P2P network	Wikipedia vote	Epinions.com
Number of nodes	6301	7115	75879
Number of edges	20777	103689	508837
Average cluster coefficient	0.0109	0.1409	0.1378

As shown in Table 2, Dataset 1 is a network for the relationships of file exchange based on a peer to peer distributed transfer protocol, Dataset 2 is a network for the voting relationships of the administrators in Wikipedia, and Dataset 3 is a network for the trust relationships among the users from a general consumer review site Epinions.com.

Fig. 4.

The influenced strength of target node (Dataset 1, $t = 20 Δ t$ ).

The parameters in the experiments include the size of seed set k, thermal conductivity a, initial influence $Q_{0}$ , the unit time of influence propagation $Δ t$ , and the time involved in influence propagation t. In our experiments, the value of k ranges from 1 to 10, $Q_{0}$ is set to 50, while α and $Δ t$ are set to be 0.2 and 0.5 respectively. Unlike linear threshold model and independent cascade model, the results of influence propagation are found to be affected by the duration of influence propagation when using HDM. To compare the performance of each algorithm, t is set to be $20 Δ t$ and $50 Δ t$ respectively.

Figures 4–6 show the influenced strength of target node on different algorithms in a short time. As demonstrated in the figures, the seed sets obtained by THGA can always exert more favorable influenced strength of target node than k-step, LND and Random. Judging from the influence results of each target node, the seed set obtained by Random presents small influence on target node. With the increase of k, the increment of target influenced strength turns to be minor. Although the increment of target influenced strength obtained by k-step increases more apparently than LND when k is increased, its target influenced strength remains to be less obvious. The great target influenced strength has been found by using LND is on Dataset 1, and it is only slightly smaller than that of using THGA. However, on Datasets 2 and 3, LND is unsatisfactory and quite inferior to THGA. The reason leading to the good performance of LND in Dataset 1 may attribute to inconsistent statistic characteristics of the datasets. Dataset 1 has a certain structural characteristic which is not in other two data sets. THGA achieves preferable target influenced strength on six different target nodes, and the increment of target influenced strength is shown to be stable with the increase of k. As k increases to a certain degree, the target influenced strength tends to be saturated and the increment decreases obviously. This indicates that under these conditions, even the number of seed nodes increases, it contributes less to the increase of target influenced strength.

Fig. 5.

The influenced strength of target node (Dataset 2, $t = 20 Δ t$ ).

Fig. 6.

The influenced strength of target node (Dataset 3, $t = 20 Δ t$ ).

Figures 7–9 reveal the comparison of the target influenced strength obtained among different algorithms in a sufficient time. As shown in the figures, the influence of seed set obtained by different algorithms spreads sufficiently with the increase of t, which further raises the target influenced strength. Specifically, Random only marginally increases the target influenced strength, and is most inferior. The average target influenced strength of k-step and LND increase 1.71 and 2.37 respectively. However, THGA always shows a superior performance and presents the biggest increment in influence intensity among the four algorithms. For THGA, the average of target influenced strength increased with extension of t is 12.60.

Fig. 7.

The influenced strength of target node (Dataset 1, $t = 50 Δ t$ ).

Fig. 8.

The influenced strength of target node (Dataset 2, $t = 50 Δ t$ ).

Fig. 9.

The influenced strength of target node (Dataset 3, $t = 50 Δ t$ ).

The running time of different algorithms is given in Table 3. The time complexities of LND and Random are $O (k \cdot n^{'})$ and $O (m)$ respectively. The main time consumed of THGA and k-step focuses on the simulation of the heat diffusion in the social network graph. The time complexity of running HDM is $O (p \cdot m)$ . THGA consists of two sequential stages, simulation of heat diffusion and selection of seed nodes. The time complexities of the two stages are $O (n \cdot (p \cdot m))$ and $O (n log n)$ respectively. The total time complexity of THGA is $O (n \cdot (p \cdot m) + n log n)$ . The time complexity of k-step is $O (n \cdot (p \cdot m + m + k q n))$ , where m is the number of the edges contained in $G (V, E)$ , n is the number of the nodes in $N^{+} (v_{i})$ , p denotes a positive integer [13], and q is the average number of sources which influence the node. Table 3 illustrates that the running time of THGA is always shorter than that of k-step on three datasets.

6. Conclusion

In this paper, based on the analysis of the problems existed in the study of personalized influence maximization, we introduce HDM to simulate the spread of information influence and thus influenced strength of target node can be directly computed. In this way, the issues that traditional models such as independent cascade model and linear threshold model forecast the node influence by relying on lots of extra processes can be overcome. Furthermore, we propose THGA to solve the HDM based personalized influence maximization problem by analyzing the propagation mechanism. Experimental results indicate that THGA is more efficient and effective.

There still exists some interesting work in the future. Firstly, it is worth further study that how to improve the efficiency of the algorithm on the premise of guaranteeing the influenced strength of a target. Secondly, with the availability of big social network data generated by online shopping, advertising and instant messaging, it is also a challenge to identify the users with satisfactory target influenced strength and wide range of influence propagation.

Table 3

Running time

	Dataset 1 (s)	Dataset 2 (s)	Dataset 3 (s)
k-step	9.34	40.47	3638.1
THGA	9.28	39.02	3369.87
LND	0.01	0.01	0.01
Random	0.0249	0.0275	0.03302

References

Chen,

Wang and

Yang, Efficient influence maximization in social networks, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 199–208. doi:10.1145/1557019.1557047.

W.X.

Chen,

Zhou and

Wu, Big social network influence maximization via recursively estimating influence spread, Knowledge-Based Systems 113(1) (2015), 143–154.

Y.C.

Chen,

W.Y.

Zhu,

W.C.

Peng,

W.C.

Lee and

S.Y.

Lee, CIM: Community-based influence maximization in social networks, ACM Transactions on Intelligent Systems & Technology 5(2) (2014), 529–544.

Doo and

Liu, Probabilistic diffusion of social influence with incentives, IEEE Transactions on Services Computing 7(3) (2014), 387–400. doi:10.1109/TSC.2014.2310216.

Doo and

Liu, Extracting top-k most influential nodes by activity analysis, in: Proceedings of the 2014 IEEE 15th International Conference on Information Reuse and Integration, IEEE, San Francisco, CA, United States, 2015, pp. 227–236.

Goyal,

Lu and

L.V.S.

Lakshmanan, CELF++: Optimizing the greedy algorithm for influence maximization in social networks, in: Proceedings of the 20th International Conference Companion on World Wide Web, ACM, Hyderabad, India, 2011, pp. 47–48.

Goyal,

Lu and

L.V.S.

Lakshmanan, SIMPATH: An efficient algorithm for influence maximization under the linear threshold model, in: Proceedings – IEEE International Conference on Data Mining, IEEE, Vancouver, BC, Canada, 2011, pp. 211–220.

Guo,

Zhang and

Fang, Personalized key propagating users mining based on LT model, Chinese Journal of Computers 37(4) (2014), 809–818.

Guo,

Zhang and

Zhou, Personalized influence maximization on social networks, in: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, ACM, 2013, pp. 199–208. doi:10.1145/2505515.2505571.

10.

Jiang,

Song,

Cong,

Wang,

Si and

Xie, Simulated annealing based influence maximization in social networks, in: Proceedings of the National Conference on Artificial Intelligence, AI Access Foundation, San Francisco, CA, United States, 2011, pp. 127–132.

11.

Leskovec,

Krause,

Guestrin,

Faloutsos,

Vanbriesen and

Glance, Cost-effective outbreak detection in networks, in: Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Jose, CA, United States, 2007, pp. 420–429.

12.

Li,

S.S.

Bhowmick,

Sun and

Cui, Conformity-aware influence maximization in online social networks, Vldb Journal 24(1) (2015), 117–141. doi:10.1007/s00778-014-0366-x.

13.

Ma,

Yang and

M.R.

Lyu, Mining social networks using heat diffusion processes for marketing candidates selection, in: 17th ACM Conference on Information and Knowledge Management, ACM, Napa Valley, CA, United States, 2008, pp. 233–242.

14.

Wang,

Chen and

Yang, Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining & Knowledge Discovery 25(3) (2012), 545–576. doi:10.1007/s10618-012-0262-1.

15.

Yu,

Wang,

Bu,

Wang,

Wu and

Chen, Friend recommendation with content spread enhancement in social networks, Information Sciences 309(10) (2015), 102–118. doi:10.1016/j.ins.2015.03.012.

16.

Zhang,

Qian and

Wang, Maximize information coverage algorithm for target market, Chinese Journal of Computers 37(4) (2014), 894–904.

A heat diffusion model based algorithm for personalized influence maximization in social network

Abstract

Keywords

1. Introduction

2. Related works

3. HDM based influence propagation

4.1. The analysis of the issues on personalized influence maximization

4.2. Target’s heat greedy algorithm

Table 2 The test datasets Dataset 1 Dataset 2 Dataset 3 Name Gnutella08 wiki-Vote Epinions1 Source P2P network Wikipedia vote Epinions.com Number of nodes 6301 7115 75879 Number of edges 20777 103689 508837 Average cluster coefficient 0.0109 0.1409 0.1378

References

Table 2
The test datasets

Dataset 1 Dataset 2 Dataset 3

Name Gnutella08 wiki-Vote Epinions1

Source P2P network Wikipedia vote Epinions.com

Number of nodes 6301 7115 75879

Number of edges 20777 103689 508837

Average cluster coefficient 0.0109 0.1409 0.1378