A novel two-step community detection approach based on community tree and the N -players cooperative game in large-scale social networks

Abstract

With the rapid development of social network, community detection has caught lots of researcher’s attention. However, the existing methods are difficult to solve mass data in growing large-scale networks. In this paper, a two-step method is proposed to cope with large-scale networks based on the construction of community tree and the $N$ -players cooperative game process. In the first stage, the community tree is constructed to initialize community detection by the similarity of nodes. Next, it performs greatly for $N$ -players cooperative game to adjust and ensure the remaining nodes or spare communities. For the transmission of the stored structure of community tree, $N$ -players cooperative game theory (NC-GT) also exhibits the excellent performance on runtime. We make the evaluations on three synthetic networks and four real-world networks and the main indicates are the modularity, NMI etc. The results show NC-GT has a stable and efficient performance on large-scale compared to other algorithms. Besides, the proposed community tree provides a more convenient way to research the flexible actions on nodes, which makes it more suitable for the dynamic networks.

Keywords

Large-scale social networks multi-stage community tree N-players cooperative game community detection

1. Introduction

The social network could be understood as the relationship structure of the connections among the actors, which is composed of limited sets or several groups of their relationships [1, 2]. And it is also faced with mass actor data, such as online social networks, Facebook, Twitter, etc. [3]. It’s meaningful for us to find out an accurate and effective way to detect the stable communities under the large-scale social networks. Currently, most algorithms, like Modularity [4], Louvain [5] and Infomap [6], perform the advantages and drawbacks in community detection. In this big data era, although some methods such as Incremental Attribute Reduction Algorithm by Lv et al. [7] are proposed to tackle large amounts of data, it is still tough to put these algorithms into use with more complex social networks, especially which is large-scale and full of huge amounts of semantic data. Therefore, it is significant to identify the community structure in large-scale networks.

In this paper, a multi-stage community detection algorithm is proposed to solve the large amount of data based on community tree and $N$ -players cooperative game theory. In the first stage, the initial communities are constructed via the tree of stored structure and similarity. Next, we proposed the NC-GT algorithm based on $N$ -players cooperative game theory. Due to the formation of the initial communities, we can adjust nodes by our algorithm quickly and accurately. The contributions of the paper are following:

•
The construction of the community tree is efficient for detection which reveals the property that almost the whole nodes are existed in the three levels. And the structure is important for accelerating the detection. Meanwhile, it provides a local environment to research the dynamic actions of nodes.
•
Based on the initial communities, we introduce an $N$ -players cooperative game algorithm to adjust the initial communities and update the information. Simultaneously, we validate our method on synthetic and real-world datasets, and compare the results with those methods in order to demonstrate the effectiveness and efficiency.

In the rest of the paper, Section 2 gives the related work. We analyze the multi-stage method and A community detection algorithm based on $N$ -players cooperative game theory in Section 3. The experiments is given in Section 4. Finally, we conclude the paper and some future works in Section 5.
2. Related work

There are many efficient methods which solve the community detection problem effectively. Generally, these scenarios can be classified from the static or dynamic calculation of the communities. For static calculation, the final division of communities could be determined by computing some of all nodes combinations whether met the global optimization. Heuristic methods based on optimization modularity, like Simulated Annealing Method [8] and Extremal Optimization [9], were put forward to reduce the time complexity. Blondel et al. gave a hierarchy greedy algorithm which could reduce the time complexity greatly [5]. To tackle the variety of structure and properties of complex social and information networks, Khomami et al. [10] put forward an algorithm based on distributed learning automata (DLACD) that equips each vertex of network with a learning automation. For the widely using of Bayesian probability model in topic discovery and other fields, Newman proposed an approach for directed network based on the hybrid model and Expectation-Maximization [11]. However, this algorithm had to specify the number of network community in advance. In order to mine communities using concise or easily interpretable descriptions rather than only depend on structural aspects, Atzmueller et al. [12] proposed a description-oriented community detection method using exhaustive subgroup discovery. They proposed several optimistic estimates of standard community quality functions to prune search space in an exhaustive branch-and-bound algorithm effectively.

Actually, the structure of large-scale social network is dynamic and full of continuous changes. Normally, it is a valid way to take a snapshot which corresponds to the static topology at one time point for dynamic network at different time points. Next, the existing static network community discovery algorithm can be used on each snapshot independently. And dynamic calculated methods mainly could be classified to the following aspects. Firstly, Wang et al. [13] proposed a method to detect overlapping community that takes the mass difference between nodes into consideration. They used PageRank algorithm to evaluate node mass and determine the community affiliation based on nodes’ positions in the inherent peak-valley structure of the topology potential field. Another routing algorithm of social network was proposed by Jia [14], which is an autonomous method using dynamic Bayesian non-negative matrix factorization to detect overlapping communities automatically. Next, methods based on particle swarm optimization are of advantage on complex social networks. An improved particle swarm optimization algorithm which has improved the parameters of velocity formula and introduced new distance calculation formula is proposed by Wu et al. [15] and is proved more efficient for function optimization problems. To optimize the modularity density, a memetic particle swarm optimization algorithm (MPSOA) introducing particle swarm optimization-based global search operator and tabu local search operator was proposed by Zhang et al. [16]. COPRA [17], proposed by Gregory, was stronger which was suitable for overlapping structure. COPRA extended the process of label propagation so that the nodes could include more label and more information of different communities. Though LPA owned a great performance on complexity of time, it was still an uncertain way. Leung et al. [18] put forward the improving LPA way, which allocated an weight for every label and the weight will be lower with the distance of propagation. And it was effective to prevent the huge communities’ forming. The other reason for the instability of LPA was the randomness. So, Lou et al. gave the (Coherent Neighborhood Propinquity, CNP) [19] to provide a more stable way. By reason of the local structure of communities, some researches concentrate on the local links of network. Lancichinetti and Fortunato [20]proposed the LFM based on local extension optimization to obtain the final division which was composed of iterated the natural communities of all nodes. Another way was GCE [21], proposed by Lee et al., which was fit on highly overlapping structure.

To some extent, these methods could acquire the community structure of the social networks in different time. However, their resistance to network noise is very poor and they must rerun algorithm on each snapshot independently which leads to the large complexity when faced with large-scale networks.

Therefore, we proposed an approach to solve the large-scale social network which datasets are more than millions. Our method, NC-GT, composed of two steps. Firstly, we construct the community tree which performs these two advantages, the efficient stored structure of networks whose nodes are active between three levels, and the other is, on this account, it is flexible for researching the dynamic nodes with this structure. Secondly, we could detect the initial communities by the similarity easily. As for the remaining single nodes, $N$ -players cooperative game theory is efficient and effective to solve the accuracy of the detection. The evaluations on the synthetic and real-world networks demonstrate the validity and efficiency of the algorithm, NC-GT.

3. A novel multi-stage communit detection method

It is important to give an exact definition of the problem. The structure of the social network is defined in Definition 1. The network nodes play different roles in the social network which is sparse. Definition 2 gives the concrete meanings of the nodes.

Given an undirected network $G=(V,E)$ , where $V$ is the set of nodes, and $E=\{e=(u,v)|u\in V,v\in V\}$ is the set of edges. The matrix $A$ whose size is $\left|V\right|\ast\left|V\right|$ is expressed by $G$ . And the value of $A$ follow this:

$\displaystyle A_{ij}=\left\{{\begin{array}[]{ll}1&e_{ij}\in E\\ 0&e_{ij}\notin E\\ \end{array}}\right.$ (1)

$D=\{V1,V2\ldots Vm\}$ could be described a division scheme in the network $G$ . A network community is a stable structure where each subdivision $V_{i}$ in the division scheme $D$ of network $G$ is divided by common certain rules.

Network node is denoted as $N=$ $<$ Id, Th, De $>$ , where Id is the serial number, Th is main information and De is the degree of the nodes. Commonly, De could be used to classify as single community node and overlapping community node.

$\displaystyle\textit{influence}\left({N_{i},D_{j}}\right)=\frac{\textit{De}% \left({N_{i},D_{j}}\right)}{\mathop{\sum}\nolimits_{j=1}^{m}\textit{De}\left({% N_{i},D_{j}}\right)}$ (2)

Equation (2) presents the effect of nodes in a certain community, $\sum_{j=1}^{m}{\textit{De}(N_{i},D_{j})}$ is the degree of the node, and $\textit{De}(N_{i},D_{j})$ gives the degree of $N_{i}$ in the community $D_{j}$ .

3.1 Initial partition method based on the community tree

Despite the social network is complexity, dynamic and with huge amounts of node, usually, the community is local which is hardly found a node belongs to the whole communities. In the topology of the social network, it is difficult to describe the locality and found the communities. So, we could convert the social network as the community tree which is easier to detect the communities.

Definition 1. (Community tree). Starting from any node $v_{i}$ as the root in the graph $G$ , we can search the network by the BFS way. If the child nodes have been visited, then pass them, until we have searched all the network so that we can get the community tree.

Algorithm 1. Construction of the Communicty Tree
Input: $G=(V,E)$ : the matrix $A$ which size is $\left\|V\right\|\ast\left\|V\right\|$
Output: the community treeCT 1. bfn $\leftarrow$ index 0 of node 12; 2. for every node $v_{i}\in V$ 3. n_visited[i] $\leftarrow$ 0; 4. end for 5. for every node $v_{i}\in V$ 6. if n_visited[i] $=$ 0 then 7. bfs(index( $v_{i})$ ) 8. $Q\leftarrow\{v_{i}\}$ 9. n_visited[i] $\leftarrow$ 1 10. while $Q\neq\{\}$ 11. $v_{i}\leftarrow\textit{Pop(Q)}$ 12. CTree( $v_{i}$ ) 13. bfn $\leftarrow$ bfn $+$ 1 14. for every edge $(v_{j},v_{j})\in E$ from 0 to n 15. if e_visited[j] $=$ 0 then 16. Push( $w, Q$ ) 17. if $j=$ 0 then 18. SN $\to$ lchild $\leftarrow$ CTN( $w$ ) 19. else 20. SN $\to$ right $\leftarrow$ CTN( $w$ ) 21. end if 22. end if 23. end for 24. end while 25. end if 26. end for

Algorithm 1. Construction of the Communicty Tree

Input:

G=(V,E)

: the matrix

A

which size is

\left|V\right|\ast\left|V\right|

Output: the community treeCT

1.
bfn $\leftarrow$ index 0 of node 12; 2.
for every node $v_{i}\in V$
3.
n_visited[i] $\leftarrow$ 0;
4.
end for
5.
for every node $v_{i}\in V$
6.
if n_visited[i] $=$ 0 then
7.
bfs(index( $v_{i})$ )
8.
$Q\leftarrow\{v_{i}\}$
9.
n_visited[i] $\leftarrow$ 1
10.
while $Q\neq\{\}$
11.
$v_{i}\leftarrow\textit{Pop(Q)}$
12.
CTree( $v_{i}$ )
13.
bfn $\leftarrow$ bfn $+$ 1
14.
for every edge $(v_{j},v_{j})\in E$ from 0 to n
15.
if e_visited[j] $=$ 0 then
16.
Push( $w, Q$ )
17.
if $j=$ 0 then
18.
SN $\to$ lchild $\leftarrow$ CTN( $w$ )
19.
else
20.
SN $\to$ right $\leftarrow$ CTN( $w$ )
21.
end if
22.
end if
23.
end for
24.
end while
25.
end if
26.
end for

The Algorithm 1 gives the construction of the community tree by the Definition 3. In the algorithm, whether a node has been visited is stored in an array n_visited[]. If node $v_{i}$ is visited, the value n_visited[i] will be 1, otherwise 0. Function bfs(index(v ${}_{i})$ ) stands for the process of BFS upon node $v_{i}$ .

According to the construction of the community tree, we give the following three features like these:

Each node in the community tree is existed in three coherent levels which provides the convenience for the next researching like detection or evolution of community;

We only make the concentration on the first emergence of the node number for avoiding the repeat and the efficiency;

The storage structure of the community tree could simplify the complex graph structure which is more beneficial.

From the construction of the community tree, it is effortless to know that most of the nodes are activated in three levels. So, the community detection can be prosperous as the overlap nodes are the focus of attention.

To find correct communities, we give the following related rules:

The breath first searching start from the root node which is as the contained community.

When comes to node $v i$ , the existence of $v i$ should be considered. If there is, that $v i$ and its parent node merged into a community can be judged by the mining the node similarity.

$\displaystyle\textit{Sim(vi,vj)}=\frac{|Ni|-|vj|}{|Nj|-|vi|}$ (3)

Initially, we give a mark of level which value is zero to every node. If the node is visited, let the value of mark change to the current level so that it is effortless to find whether visited in the pre-level.

It is obvious to know there are still some contained communities after once visit. Therefore, we should consider the border node formed in these communities.

The Algorithm 2 gives the initial division of the community tree following the above rules. This is a rough division of the community tree to prepare for more precise division in the next steps.

Algorithm 2. Initial Division of the Community Tree
Input: the community treeCT
Output: the initial division of CT $D=\{D1,D2,\ldots,Dm\}$
1. Init(Q) 2. Q.Enqueue(CT) 3. while Q.Empty() ! $=$ null 4. DN $\leftarrow$ Q.Dequeue() 5. if DN.flag ! $=$ $-$ 1 then 6. DN.flag $\leftarrow$ $-$ 1 7. end if 8. if DN->lchild ! $=$ null and DN->lchild.flag ! $=$ $-$ 1 9. if DN->lchild.data $=$ DN->lchild.flag then 10. if Sim(DN, DN->lchild)> $\alpha$ then 11. DN->lchild.flag $=$ $-$ 1 12. DN->next $=$ DN->lchild 13. end if 14. else 15. Q.Enqueue(DN->lchild) 16. DN->lchild.flag $\leftarrow$ DN->lchild.data 17. DNLR $\leftarrow$ DN->lchild->right 18. if DNLR! $=$ null and DNLR.flag ! $=$ $-$ 1 and 19. DNLR.flag ! $=$ DNLR.data then 20. if Sim(DNLR, DNLR ->lchild) $>$ $\alpha$ then 21. DNLR ->lchild.flag $=$ $-$ 1 22. DNLR ->next $=$ DNLR ->lchild 23. end if 24. else 25. Q.Enqueue(DNLR) 26. DNLR.flag $\leftarrow$ DNLR.data 27. DNLR $\leftarrow$ DNLR->right 28. end if 29. end if 30. end if 31. end while

Algorithm 2. Initial Division of the Community Tree

Input: the community treeCT

Output: the initial division of CT

D=\{D1,D2,\ldots,Dm\}

Init(Q) 2.

Q.Enqueue(CT)

while Q.Empty() ! $=$ null

DN $\leftarrow$ Q.Dequeue()

if DN.flag ! $=$ $-$ 1 then

DN.flag $\leftarrow$ $-$ 1

end if

if DN->lchild ! $=$ null and DN->lchild.flag ! $=$ $-$ 1

if DN->lchild.data $=$ DN->lchild.flag then

10.

if Sim(DN, DN->lchild)> $\alpha$ then

11.

DN->lchild.flag $=$ $-$ 1

12.

DN->next $=$ DN->lchild

13.

end if

14.

else

15.

Q.Enqueue(DN->lchild)

16.

DN->lchild.flag $\leftarrow$ DN->lchild.data

17.

DNLR $\leftarrow$ DN->lchild->right

18.

if DNLR! $=$ null and DNLR.flag ! $=$ $-$ 1 and

19.

DNLR.flag ! $=$ DNLR.data then

20.

if Sim(DNLR, DNLR ->lchild) $>$ $\alpha$ then

21.

DNLR ->lchild.flag $=$ $-$ 1

22.

DNLR ->next $=$ DNLR ->lchild

23.

end if

24.

else

25.

Q.Enqueue(DNLR)

26.

DNLR.flag $\leftarrow$ DNLR.data

27.

DNLR $\leftarrow$ DNLR->right

28.

end if

29.

end if

30.

end if

31.

end while

3.2 Dynamic adjustable algorithm based on the agent game

From part A, some exact communities and overlapping nodes which are hard to judge since the nodes is in the several communities. We put forward the $N$ -players cooperative games model to solve the overlapping nodes. Several communities which are associated with overlapping node are regarded as the players. The goal is the pursuit of utility maximization of the whole community. We give the game model as follows:

The community formed by independent overlapping node makes its correlated $n$ communities as the game party. Given the definition of the game: $G=$ $<$ $\Psi$ , $S$ , $U$ $>$ . Here, $\Psi=\{p_{1},p_{2},\ldots,p_{n}\}$ is the set of the players. And $S=\{s1,s2\}$ are the strategies which the game parties can choose. Concretely, $S1$ and $S2$ represent the strategies $\{\textit{Accept$,$Reject}\}$ respectively. $U:s\to R^{\psi}$ could be used to express the payoff of every pure strategy where $u(s)=\{u_{1}(s),u_{2}(s)\}$ .

Now, we consider the main utility for every player is the increase or decrease of the modularity itself whatever strategy it chooses. Modularity [2] is defined as follows which is to measure the quality of the detecting communities.

$\displaystyle Q=\frac{1}{2m}\sum\limits_{ij}{\left[A_{ij}-\frac{k_{i}k_{j}}{2m% }\right]}\;\delta c_{i},c_{j}$ (4)

Where $A_{ij}$ is an element of the adjacency matrix, $\delta_{i,j}$ is the Kronecker delta symbol, and $c_{i}$ is the label of the community to which vertex $i$ is assigned.

So, it can be used to convey the payoff function of every game part $i$ by modularity $Q$ . The game party decides whether to accept an overlapping node by adding it which results in the utility gain of modularity according to:

$\displaystyle\{C\}\leftarrow\{C\}\cup n_{i}$ (5)

And the formulation of $u_{i}$ is like this:

$\displaystyle u_{i}^{\prime}\leftarrow\max\{u_{s_{\textit{accept}}},u_{s_{% \textit{reject}}}\}$ (6)

$u_{s_{i}}$ is calculated by $u_{s_{i}}\leftarrow Q^{\prime}\cup Q_{2}$ which means the utility via using the modularity.

Since the community detection is to get the max average modularity, the $N$ -players may be formed to an alliance party for the max whole benefit. In our framework, the said game model should be formed to the $N$ -players cooperative games. Everyone’s goal is to make the max contribution for the whole community. Here gives the replaced utility of the player as follows:

Definition 2. (Contribution to modularity). It is expressed for the current node to join or leave one community which result in the improvement of the whole modularity, we use the proportion to calculate where the $u_{i}$ is the utility of the game player.

$\displaystyle\eta_{{}_{i}=}\frac{u_{i}}{\sum\limits_{i=1}^{N}{u_{i}}}$ (7)

Now, it is vital to discuss the solution of the $N$ -players cooperative game. For $n$ players, $N=\{1,2,\ldots,n\}$ , the any subset $S$ can be called an alliance of the $N$ . Here we mainly considerate the transformable utility-(TU) which is the profit of any player has the same change with the change of utility under the free allocation. Definition 5 describes the characteristic function of the game which is related to express TU.

Definition 3. (Characteristic function). If the players’ set of game $N=\{1,2,\ldots,n\}$ is the real-valued function which is defined on the subset of the $N$ , $v(s)$ is the characteristic function or coalitional function in respect of strategy $S$ if :

$\displaystyle v(\emptyset)=0,$ (8) $\displaystyle v(N)\geqslant\sum\limits_{i\in N}{v(\{i\})}$

Given the above definition, the said game could be expressed as the characteristic function form like: $G=[N,v]$ . If the establishment of $S$ is independent from the alliance’s transaction behavior of interests, then $v(S)$ will be the biggest gain of $S$ . Under the circumstances, we introduce a method to calculate the characteristic function. The valuation method is to give a reasonable allocated value which is unique by axiomatic system. The index of power like Shapley value [22] is used to explain the concept of the solution in $N$ -players cooperative games.

Definition 4. (Shapley-Shubik index of power). Given an $n$ dimensional vector $\Phi(v)=(\varphi_{1}(v),\varphi_{2}(v)$ , $\ldots,\varphi_{n}(v))$ , which can be defined as the Shapley value of the cooperative game $G=[N,v]$ .

$\displaystyle\varphi_{i}(v)=\sum\limits_{s\subseteq N}{\frac{(n-\left|S\right|% )!(\left|S\right|-1)!}{n!}[v(S)-v(S\backslash\{i\})]}$ (9)

where $|S|$ is the number of the player. $(|S|-1)!$ is the number of coalition which is exclusive of player $i$ after formed coalition $S$ . $(n-|S|)!$ expresses the possibility of coalition $N\backslash S$ .

So, $\frac{(n-\left|S\right|)!(\left|S\right|-1)!}{n!}$ gives the probability of emerging on coalition $S$ , $v(S)-v(S\backslash\{i\})$ is the marginal contribution which from player $i$ to coalition $S$ . Here, if $i\notin S$ , there is no marginal contribution for player $i$ which gives the $v(S)-v(S\backslash\{i\})$ equals to zero.

It is significant to analysis the following three axioms which is the establishment of the said Shapley value’s definition.

Axiom 1. (Symmetry axiom). For replacement $\pi$ ,

$\displaystyle\varphi_{\pi i}(\pi v)=\varphi_{i}(v).$ (10)

Axiom 2. (Efficiency axiom). For every brace $D$ of $G$ ,

$\displaystyle\sum\limits_{i\in D}{\varphi_{i}(v)=v(D)}.$ (11)

Axiom 3. (Additive axiom). For any two cooperative games

$\displaystyle G_{1}=[N,v]\ \text{and}\ G_{2}=[N,w],\text{if}\ i\in N,$ (12) $\displaystyle\varphi_{i}(v+w)=\varphi_{i}(v)+\varphi_{i}(w)$

where $(v+w)(S)=v(S)+w(S)$ .

According to the unique Shapley value from the analysis, each component $\varphi_{i}(v)$ could be seen as the weight of the players in the cooperative game so that the solution is easy to get. The following Algorithm 3, NC-GT, describes the method of integrated community detection.

Algorithm 3. NC-GT: Community Detection based on Game Theory
Input: the initial communities $D=\{D1,D2,\ldots,Dm\}$
Output: the final communities 1. for all communities D then 2. isVisited $\leftarrow$ 0 3. end for 4. for all communities D then 5. c $\leftarrow$ Current_communities 6. if isVisited ! $=$ 0 then 7. N_Players(c) $\leftarrow$ Search_Related_Communities( $D$ ) 8. $\Phi(v)\leftarrow$ Calculate_ Shapley_index(N_Players(c)) 9. Update communities by $\Phi(v)$ 10. isVisited $\leftarrow$ 1; 11. end if 12. end for

Algorithm 3. NC-GT: Community Detection based on Game Theory

Input: the initial communities

D=\{D1,D2,\ldots,Dm\}

Output: the final communities

for all communities D then 2.

isVisited $\leftarrow$ 0

end for

for all communities D then

c $\leftarrow$ Current_communities

if isVisited ! $=$ 0 then

N_Players(c) $\leftarrow$ Search_Related_Communities( $D$ )

$\Phi(v)\leftarrow$ Calculate_ Shapley_index(N_Players(c))

Update communities by $\Phi(v)$

10.

isVisited $\leftarrow$ 1;

11.

end if

12.

end for

3.3 Analysis of the algorithms

Retrospect the above algorithms, Algorithm 1 gives the construction of the community tree mainly by one-time travel with the complex of $O(\left|N\right|+\left|E\right|)$ . As for Algorithm 2, it is the initial division of community tree consisting of calculating the $\textit{Sim}(v_{i},v_{j})$ between the current searching nodes and dividing the nodes by $\textit{Sim}(v_{i},v_{j})$ . Absolutely, the main complexity of the algorithm is caused by the travel in the community tree which is $O(n\ \log\ n)$ . Though the complexity cannot reach to linear, the construction of community tree provides a great foundation for analysis the dynamic nodes.

The main point is to divide the final communities precisely, and Algorithm 3 gives ultimate result. It is not hard to get the complexity is $O(n\text{log}n)$ which is similarity to the Algorithm 2. Algorithm 3 gives the certain solution to the community detection.

4. Experiments

4.1 Datasets and settings

We consider evaluating our proposed method on synthetic and real-world networks to presents its performances. The synthetic networks are generated randomly based on the LFR (Lancichinetti Fortunato Radicchi) [23] which is easily to control the distribution of degree and community size of the networks and demonstrate the precise of the algorithm of the community detection. The following Table 1 gives the synthetic datasets including some parameters we use for this paper. Here, the mixing parameter $\mu$ is the fraction of each node outside its community which controls the difficulty of community separation.

Table 1
Datasets of synthetic networks

DataSets	$\left\|\mbox{V}\right\|$	$\left\|\mbox{E}\right\|$	$\mu$	AD
sythet-10w	100000	1984900	0.4	39.70
sythet-50w	500000	9831289	0.4	39.33
sythet-100w	1000000	19641382	0.4	39.28

As for real-world networks, it is more significant for us to demonstrate the effectiveness of algorithm. We collect the following datasets which are available from Stanford Network Analysis Project (SNAP) [24].

Table 2

Datasets of real-world networks

DataSets	$\left\|\mbox{V}\right\|$	$\left\|\mbox{E}\right\|$	Class	AD
Amazon	334864	925872	151037	5.530
web-BerkStan	685320	7600595	$-$	22.180
Road	1088092	1541898	–	2.834
Wiki-Talk	2394385	5021410	–	4.190

The algorithms were evaluated on the same environment with 8 G RAM and Inter CPU 2.40 GHz for the simulation. And the following community detection methods are used as the comparison:

•

Modularity [4]. Since the modularity was proposed to measure the clustering quality, and one of the most popular detection scenarios is known as “modularity”. The methods show the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network.

•

Louvain [5]. The Louvain is different from the traditional methods like “modularity” which is based on a hierarchical greedy algorithm to find community, the algorithm mainly includes two steps. Hierarchical greedy algorithm to communities found is extremely intuitive and easy to implement. It is known that in the sparse network, time complexity of the algorithm is linear for large scale discovery in the complex network of communities.

•

Infomap [6]. The Infomap based on theory of information tries to use the random walks which will generate the corresponding data steam as the agent of the information transmission on the network. And the quantity of information generated by the random walks is measured via the length of code of average random walks.

•

LabelRankT [25]. LableRankT is an online distributed algorithm for detection of communities in large-scale dynamic networks through stabilized label propagation. Since the algorithm ask for several parameters in advance, and the paper [25] gives the best performing values.

4.2 Evaluation

Since the most popular measurement of the community detection on networks is Modularity [4]. However, it has been shown that modularity is not perfect and performs the unavailable when comes to real-world. The Eq. (4) gives the specific definition.

As for the networks which communities have been known, NMI (normalized mutual information) is used for measuring the performance of the algorithms. NMI is defined as follows:

$\displaystyle\textit{NMI}=\frac{I(X,Y)}{\sqrt{H(X)H(Y)}}$ (13)

Where $I(X,Y)$ is the mutual information between $X$ and $Y$ , then $H(X)$ and $H(Y)$ makes the entropies of $X$ and $Y$ respectively. NMI reflects the closeness between the detected communities with the real communities.

However, it is necessary to consider the number of discovered community via the algorithms. The result of the detection is always the apparent indicator to compare the precise of the algorithms.

4.3 Results and analysis

4.3.1 The evaluations on the synthetic networks

Figure 1.

The influence of mixing parameters $\mu$ .

Figure 2.

The influence of average degree $k$ .

Figure 1 gives comparisons in impacts of NMI among algorithms and different scale of synthetic networks from the mixing parameter $\mu$ . When $\mu=$ 0.4, most algorithms reach the highest point which accounts for the best values. Modularity and Louvain express the poor performances with large fluctuation which perform the state of decline. While other three algorithms present slight certain decrease at the point 0.8 with a stable tendency overall. Though NC-GT makes disadvantage compared to Infomap with the lower $\mu$ , it gets the great performance as a whole.

We also evaluate the different average degrees in synthetic networks and exhibit the performances on the NMI among algorithms. With the increase of the amounts of the node, there are merely changes in the different scales. From any networks, all of algorithms excepting Infomap keep a well and stable performance. As for Infomap, it is abnormal when it reaches to 10 and it has an increase when the scale of network gets stronger. Besides, we found that Modularity and Louvain possess the good effect with the change of average degree, while they could not keep the same performance on the mixing parameter $\mu$ which says the algorithms has its shortages on complex datasets. Combined Figs 1 and 2, we may conclude that NC-GT keeps a fine property over other algorithms overall.

4.3.2 The simulations on the real-world networks

Figure 3.

The results of modularity on datasets.

Modularity is the most popular measurement which we evaluate on the four real-world datasets. Compared to synthetic networks, the real-world’s properties are more complex and irregular than the synthetics. Besides, NC-GT and Louvain exhibit great performance on different datasets. Compared from multi-aspects, when we concentrate on any one of the algorithms, the results of the modularity are very approximate which reach the phenomenon that the influence of datasets on community detection is slight.

Figure 4.

The results of NMI on datasets.

We observe that Infomap and LabelRankT have a perishing performance, while the others maintain the goodness on the evaluation. However, the best point is only 0.856 which illustrates all of algorithms are worse than the synthetic networks when they come to the real-world networks. Combined with Fig. 3, the Louvain and NC-GT get the great and stable performance with the high NMI compared with synthetic networks. Infomap has exhibited the fluctuated and great performance on synthetic networks, while it pays the worst performance and which reaches at 0.2. We get the conclusion Infomap does not considerate the complex ties among real-world networks. The community detection in real-world datasets has to combine the social properties.

Figure 5.

Runtime analysis.

It is significant to analyze the runtime of algorithms to demonstrate the efficiency. From Fig. 5, we could Modularity perform the worst with the increase of scale of networks which is fit on small-scale datasets. Our algorithm, NC-GT, is faster than modularity and a considerable to compare with Louvain, Infomap and LabelRanT. NC-GT is suitable for community detection on large-scale networks, especially the online social networks which possess the large amount of nodes and edges and complex ties of the nodes.

5. Conclusion and future work

The increasing challenge in community detection is more and more common. In this paper, we construct the community tree to store the structure of network which could obtain the local property of nodes. And based on the unique structure, the initial detection is more efficient and easier. Meanwhile, $N$ -players cooperative games in the remaining nodes and spares communities are accuracy for adjustment and detection. The results on synthetic and real-world networks show the validity and flexibility when faced with large-scale networks. While, to join or quit the network of the nodes and the ties of the edges generate the dynamic social network. Here, the focus on the solution of large-scale, we are trying to concentrate on the dynamic action of local area’s nodes. Because of the “three level” property, it’s meaningful and urgent for us to find out an accurate and effective way to detect the stable communities under the large-scale dynamic social network.

Footnotes

Acknowledgments

Natural Science Foundation of China (61572036), Natural Science Foundation of Anhui Province of China (1708085MF156), Science Foundation for The Excellent Youth Scholars by Anhui Province, China (2009SQRZ127), CERNET Next Generation Internet Creative Project of China (NGII20170305).

References

Wasserman

and Faust

, Social network analysis: Methods and applications[M]. Cambridge university press, 1994.

Brandes

Borgatti

S.P.

and Freeman

L.C.

, Maintaining the duality of closeness and betweenness centrality[J], Social Networks 44 (2016), 153–159.

Wei

Luo

et al., Knowle: a semantic link network based system for organizing large scale online news events[J], Future Generation Computer Systems 43 (2015), 40–50.

Newman

M.E.J.

, Modularity and community structure in networks[J], Proceedings of the National Academy of Sciences 103(23) (2006), 8577–8582.

Blondel

V.D.

Guillaume

J.L.

Lambiotte

et al., Fast unfolding of communities in large networks[J], Journal of Statistical Mechanics: Theory and Experiment (10) (2008), P10008.

Rosvall

and Bergstrom

C.T.

, Maps of random walks on complex networks reveal community structure[J], Proceedings of the National Academy of Sciences 105(4) (2008), 1118–1123.

Qian

and Yue

, Incremental attribute reduction algorithm for big data using MapReduce[J], Journal of Computational Methods in Sciences and Engineering 16(3) (2016), 641–652.

Guimera

Sales-Pardo

and Amaral

L.A.N.

, Modularity from fluctuations in random graphs and complex networks[J], Physical Review E 70(2) (2004), 025101.

Duch

and Arenas

, Community detection in complex networks using extremal optimization[J], Physical review E 72(2) (2005), 027104.

10.

Khomami

M.M.D.

Rezvanian

and Meybodi

M.R.

, Distributed learning automata-based algorithm for community detection in complex networks[J], International Journal of Modern Physics B 30(8) (2016), 1650042.

11.

Newman

M.E.J.

and Leicht

E.A.

, Mixture models and exploratory analysis in networks[J], Proceedings of the National Academy of Sciences 104(23) (2007), 9564–9569.

12.

Atzmueller

Doerfel

and Mitzlaff

, Description-oriented community detection using exhaustive subgroup discovery[J], Information Sciences 329 (2016), 965–984.

13.

Wang

Z.-X.

Z.-C.

Ding

X.-F.

and Tang

J.-H.

, Overlapping community detection based on node location analysis[J], Knowledge-Based Systems 105 (2016), 225–235.

14.

Jia

, A social networks routing algorithm of resisting sybil attack based on P2P, Journal of Computational Methods in Sciences and Engineering 6(4) (2016), 877–898.

15.

Song

Liu

et al., Particle swarm optimization algorithm based on parameter improvements[J], Journal of Computational Methods in Sciences and Engineering 17(3) (2017), 557–568.

16.

Zhang

Hei

Yang

et al., A memetic particle swarm optimization algorithm for community detection in complex networks[J], International Journal of Pattern Recognition and Artificial Intelligence 30(2) (2016), 1659003.

17.

Gregory

, Finding overlapping communities in networks by label propagation[J], New Journal of Physics 12(10) (2010), 103018.

18.

Leung

I.X.Y.

Hui

Lio

et al., Towards real-time community detection in large networks[J], Physical Review E 79(6) (2009), 066107.

19.

Lou

and Zhao

, Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J], Physica A: Statistical Mechanics and its Applications 392(14) (2013), 3095–3105.

20.

Lancichinetti

and Fortunato

, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J], Physical Review E 80(1) (2009), 016118.

21.

Lee

Reid

McDaid

et al., Detecting highly overlapping community structure by greedy clique expansion[J], arXiv preprint arXiv:1002.1827, 2010.

22.

Roth

A.E.

, The Shapley value: essays in honor of Lloyd S. Shapley[M]. Cambridge University Press, 1988.

23.

Lancichinetti

Fortunato

and Radicchi

, Benchmark graphs for testing community detection algorithms[J], Physical Review E 78(4) (2008), 046110.

24.

Jure

, Stanford large network dataset collection[OL]. http://snap.stanford.edu/data/index.html, 2013.

25.

Xie

Chen

and Szymanski

B.K.

, LabelrankT: Incremental community detection in dynamic networks via label propagation[C]//Proceedings of the Workshop on Dynamic Networks Management and Mining. ACM, 2013: 25–32.

A novel two-step community detection approach based on community tree and the N -players cooperative game in large-scale social networks

Abstract

Keywords

1. Introduction

3. A novel multi-stage communit detection method

4. Experiments

4.1 Datasets and settings

Table 1 Datasets of synthetic networks

4.3.1 The evaluations on the synthetic networks

Footnotes

Acknowledgments

References

Table 1
Datasets of synthetic networks