An efficient community discovery algorithm based on synchronous dynamic model

Abstract

Community detection is an important way to describe the evolution of network events. In order to study.how to differentiate network community structure accurately and effectively, and solve the problem of the Sync clustering algorithm directly connected nodes without common neighbor nodes existing similarity underestimated tendency, and the synchronization time being too long, we put forward a method which breaks edge disconnection between connected nodes directly and add auxiliary nodes. We can think that the two nodes are connected by the secondary node and the edge of the two nodes connected respectively, and then realize the improvement of node similarity. Secondly this paper uses neighborhood radius to divide community, and detect the community before the node object has reacded fully synchronous. Simulation experiments are done respectively on the artificial data and real data sets generated, and the results show that the improved algorithm is more accurate to effectively find community structure compared with the original algorithm.

Keywords

Sync clustering algorithm neighbors similarity neighborhood radius community structure

1. Introduction

Wireless Mesh network is an important wireless broadband access technology. Its advantges are the self-organiing, large coverage, easy maintenance, good network scalability, and low cost, and it is the important option of Internet for the “last kilometer” extension [1] mesh customer base has resulted in the server load stress. Researches indicate that community can be explored according to the geographic information of P2P network node society, and guide them in the same community for data exchange, which can alleviate the load on the server, so community detection plays an important role to relieve the load on the server.

Community structure of internal corporate links closely, and sparse between corporate connection [2, 3]. So far, scientists have come up with a large amount of network community discovery algorithms such as optimization algorithm based on the module, hierarchical clustering, spectral clustering and Sync clustering algorithm [3, 4, 5, 6, 7, 8, 9, 10]. There are some defects in these methods such as community number and some parameters. Sync algorithm thinks that the connecting edge between two nodes and no public neighbors have no similarity, this may underestimate the similarity between them, and the synchronization algorithm cost too much time to deal with mass of data. Regarding these problems, this paper considers the impact on the similarities between connected nodes directly, and improves the similarity of Sync clustering algorithm. It can detect the community structure before complete synchronization object by using the principle of neighborhood closures and module changing trend at the same time, which reduces the time of the dynamic interaction of node objects greatly, and this method does not need to know the number of the community in advance.

2. Sync clustering algorithm

Huang et al. propose a community discovery algorithm which bases on synchronous dynamic model (Sync) [11]: Given an undirected weighted networks $G=(V,E,W)$ where $V$ represents the set of vertices in the graph and $E$ represents the set of edges and $W$ represents the weights of the edges. If we regard each node of the network as a vibrator, and each phase value of the oscillator as the OX shaft corresponding coordinate values. The node object $x$ coordinates the dynamic change of formula in each dimension over time under the effect of local coupling:

$\displaystyle x(t+1)=x(t)+\frac{1}{N_{S}(x(t))}\cdot\sin(y(y)-x(t))\cdot% \mathop{\sum}\limits_{y\epsilon N_{S}(x(t))}\frac{\Sigma\tau\epsilon\tau t(x)% \cap\tau(y)^{w(x,z)\cdot w(y,z)}}{\sqrt{\Sigma\tau\epsilon\tau(x)^{w^{2}(x,z)}% }\cdot\sqrt{\tau\epsilon\tau(y)^{w^{2}(y,z)}}}$ (1)

The oscillator phase values of convergence are regarded as a community finally. If it is a undirected network, Eq. (1) is equivalent to Eq. (2):

$\displaystyle{x}\left(t+1\right)=x\left(t\right)+\frac{1}{N_{S}\left(x\left(t% \right)\right)}\cdot{{\sin}\left(y\left(t\right)-x\left(t\right)\right)\ }% \cdot\sum_{y\epsilon N_{s}\left(x\left(t\right)\right)}{\frac{\tau\left(x% \right)\cap\tau\left(y\right)}{\sqrt{\tau\left(x\right)\cdot\tau\left(y\right)% }}}$ (2)

It uses the clustering order parameter to describe oscillator level of synchronization between the nodes [12]. The formula is as follows $\left(0\leqslant s\leqslant 1\right)$ :

$\displaystyle{s}{\cdot}e^{i\emptyset}=\frac{1}{n}\sum^{n}_{j=1}{e^{i{\emptyset% }_{j}}}$ (3)

Sync clustering algorithm uses the $n$ umber of public neighbor nodes to measure the similarity between nodes in an undirected network, which defines as follows:

$\displaystyle S_{xy}{=}\frac{\tau\left(x\right)\cap\tau\left(y\right)}{\sqrt{% \tau\left(x\right)\cdot\tau\left(y\right)}}$ (4)

$\tau(x)$ represents the neighbors of node $x$ , and $\tau(y)$ represents the neighbors of node $y\cdot\tau(x)+\tau(y)$ represents public neighbor nodes of node $x$ and $y$ . As we can see from Eq. (4), Sxy can more measure the similarity between them accurately for the not directly connected nodes. But for the nodes which directly connected and has no public neighbor nodes, Sxy is 0 because of the molecule of Eq. (4) is zero. Connecting between nodes without public neighbors is ubiquitous in the same community, and the similarity between them should not be zero in many cases.

When using the Sync synchronization algorithm in the process, under the effect of partial synchronization [13], as time goes on, more and more node objects are synchronized, and the value of is becoming bigger and bigger. When nearly reaches 1 of the preset value, the clustering will end, and now we think the synchronization of node objects to be completed, and the node objects in the same community move to the almost same coordinate point. However, to achieve synchronization is a relatively long process of dynamic synchronization. The efficiency of the algorithm is low. For the sake of easy, symbols in this article are introduced in Table 1.

3. An efficient community discovery algorithm based on synchronous dynamic model

3.1 The improved similarity measure

There are similarities that tend to be underestimated in the Sync algorithm. The article considers the similarity between nodes from two cases: between the connected two nodes and endless connected, as shown the nodes $x$ , $y$ in Figs 1 and 2. In order to accurately depict similarity between the nodes, we disconnect the edge (x,y) and add auxiliary node con the case of the connected nodes, as shown in Fig. 3. Now, we can think that the edge (x,y) consists the edges (x,c) and (c,y). That is to say, both A(x,y) and B(y,x) are 0 in the adjacency matrix A, and join the secondary node c which corresponds to arow and column. Assuming that Fig. 3 corresponds to the adjacency matrix A, new rows and columns are 0 except A (x,c), A (y,c), A (c,x), A (c,y).

Table 1
The symbols are used in this article

Symbol	Definition
Y	Node set
X	An element mode in the collection
${x}({t})$	The renewal value of object x at time step t
Y	The total number of edges in the network
n	The number of nodes
s	Clustering of order parameter
p	The total number of network society
dj	The total degree in th community
S	The radius of the synchronization
${{N}}_{{S}}({x})$	S-neighborhood of the object x
i	The i-th nodes
${{\theta}}_{{i}}$	The phase of the j-th node
${\varphi}$	The average phase
Q	Modularity evaluation function
ei	The number of edges in i-th community
${\tau}({x})$	The neighbor node number of node x

Figure 1.

An edge between x and y.

Figure 2.

No edge between x and y.

Figure 3.

Adding auxiliary c.

If the adjacency matrix of the network is A, Eq. (4) is equivalent to Eq. (5):

$\displaystyle S_{xy}=\frac{\sum^{n}_{k=1}{A_{xk}\cdot A_{ky}}}{\sqrt{\tau\left% (x\right)}\cdot\tau\left(y\right)}$ (5)

The similarity of two nodes after adding a secondary node c is Mxy, put the adjacency matrix A into the Eq. (5):

$\displaystyle M_{xy}{=}\frac{\sum^{n+1}_{k=1}{A^{\prime}_{xk}}\cdot A^{\prime}% _{ky}}{\sqrt{\tau\left(x\right)\cdot\tau\left(y\right)}}=\frac{1+\sum^{n}_{k=1% }{A_{xk}\cdot A_{ky}}}{\sqrt{\tau\left(x\right)\cdot\tau\left(y\right)}}$ (6)

In the Eq. (6), 1 means the adding common neighbor node c. Other public node numbers are equal to the public node numbers with not auxiliary node, acted, we can use Eq. (7) to calculate. Therefore, the similarity of any node can be represented by Eq. (7).

$\displaystyle M_{xy}{=}\frac{1+\sum^{n}_{k=1}{A_{xk}\cdot A_{ky}}}{\sqrt{\tau% \left(x\right)\cdot\tau\left(y\right)}}$ (7)

Put Eq. (7) into Eq. (2).and get Eq. (8).

$\displaystyle{x}\left(t+1\right)=x\left(t\right)+\frac{1}{N_{\$}\left(x\left(t% \right)\right)}\cdot{{\sin}\left(y\left(t\right)-x\left(t\right)\right)\ }% \cdot\sum_{y\epsilon N_{S}\left(x\left(t\right)\right)}{\frac{A\left(x,y\right% )+\sum^{n}_{k=1}{A_{xk}\cdot A_{ky}}}{\sqrt{\tau\left(x\right)\cdot\tau\left(y% \right)}}}$ (8)

3.2 Two kinds of similarity comparison

Figure 4 is a simple network diagram which contains two communities. One community contains a, b, c, d, and the other contains e, f, g, h. Table 2 is the similarity of sequence got by two kinds of similarity index. Sxy represents improved similarity index, and Mxy represents unimproved similarity index. We can see from Table 2 that node a and node c have the highest similarity in Sxy. This is due to node a and node c have the maximum number of neighbors, the second is the g. Node a and node b are connected directly but have no neighbors, their similarity is 0. This is not conform to the network’s actual division. Sxy only considers the shared neighbor nodes, and it underestimates the directly connected neighbor nodes without similarity. For Mxy, node a and node c have the highest similarity, followed by d, b or g. The similarity between node a and node b is not zero when we use Mxy to calculate. The improved similarity coefficient can better reveal similarity between nodes in complex networks from this simple case.

Table 2
Order table of similarity of nodes

Node	Sxy	Mxy
a	c, g	c, d, b or g
b	d, e or h	a or c or d or e or h, g
c	a, g	a, d, b or g
d	b	b, a or c
e	h, b	h, f, g or b
f	g	g, e or h or c or a, b
g	f or a, c	f, e or h or c or a, b
h	e, b	e, f, b or g

Figure 4.

A simple network.

3.3 Partial synchronization convergence criteria

Definition 1. ($-neighborhood closure [14]) Assume that the node object set is Y ${}^{\prime}$ ${\in}$ Y. In the process of simultaneous clustering, if ${\forall}$ x; y ${\in}$ Y ${}^{\prime}$ satisfies x ${\to}$ $ y, moreover, if x ${\to}$ $ y then z ${\in}$ Y ${}^{\prime}$ , so we can say Y ${}^{\prime}$ is a $-neighborhood closure. That is to say there are N$(x) $=$ Y ${}^{\prime}$ for any node object x ${\in}$ Y ${}^{\prime}$ .

Figure 5 simply describes the meaning of $-neighborhood closure. This paper mainly studies the nodes on the OX axis movement. There are nodes a,b,c,d in $-neighborhood of the node a, that is N$(a) $=$ ${\{}$ a; b; c; d ${\}}$ . If N$(a) $=$ N$(b) $=$ N$(c) $=$ N$(d) $=$ ${\{}$ a; b; c; d ${\}}$ meet the Definition 1, then ${\{}$ a; b; c; d ${\}}$ is a $-neighborhood closure. Interaction among nodes a, b, c, d in the process of partial synchronization is not affected by other nodes, so they will form a community. e and f are the nodes which are outside of the neighborhood closure.

The algorithm of this article uses $-neighborhood closure instead of the order parameter s in Sync clustering algorithm, to detect the community structure before arriving in complete synchronization object, thereby significantly reducing the number of times synchronization among the node objects, and improves the efficiency of the algorithm.

Figure 5.

$-neighborhood closure.

Theorem 1. Assume that the node object set is Y ${}^{\prime}$ ${\in}$ Y. If is a $-neighborhood closure, then all the objects of Y in the local dynamic synchronization process will eventually reach complete synchronization.

Proof. Each node object is effected only by its $-neighbors according to Eq. (8). When N$ (x) is a $-neighborhood closure,the nodes in the object set Y are $-neighborhood closures each other, and the node object in $-neighborhood closure meet the transitive closure properties, so any objects are in the Y only forced by other objects in the collection, and the node objects outside of the set have no effect on it, therefore the node objects in the Y only move in the area, moreover the edge nodes far from the center of move toward the center of the $-neighborhood under the impact on the other nodes of the set. This makes the collection radius is shrinking, and will eventually reach synchronization completely.

Theorem 2. Given a parameter [15, 16, 17, 18], the object in the node object set Y will be formed in several $-neighborhood closure with the effect of partial syn-chronizatio n coupling.

Proof. Given a $- a neighborhood parameter in the node set Y. Any object xi $-neighborhood N$(xi) of the collection is a subset of the set Y. If There shown in Fig. 6, x and g are unstable data. The unstable node object x and the stable objects in the set of Y are different. It is influenced by on not only the data in set N$(x) but also the data in set is the following: (1) Movement towards a certain N$(xi). This separates oneself from other N$ (x) to his influence. (2) The multiple node objects in N$(x) are influenced by x. This will gradually move closer to the $-neighborhood of x, and the final will be merged into one N$ (x). The Unstable data in set Y will always move in the light of the above two cases, until these data become stable. So any nodes of set Y in the process of synchronization will reach $-neighborhood closures.

Figure 6.

Unstable data.

3.4 Algorithm realization step

Given an undirected network G $={<}$ V,E ${>}$ , first, put the node objects on OX axis according to the similarity of the node density and the spacing of nodes are equal. In this algorithm, we make the node co-ordinates to start from 0, and make the spacing to be 0.1, and then sort according to the node density similarity, finally cluster on the node object synchronization. The following are specific steps.

Step 1
Set the value of the parameter $;
Step 2
According to Eq. (8), we can get the new node coordinates after synchronization of each node within its $-neighborhood radius of node;
Step 3
We can get the new node coordinates according to step 2, then make the nodes which has not been divided into a community and its $-neighbor-hood radius of node into a community in turn;
Step 4
Calculate the classification results of the modularity Q, and compare with the last partition modularity. If the Q is always declining, then the result is the optimal community, and output the optimal community structure. If Q is not declining,then go to step 5.
Step 5
Increase the value of $, and repeat step 2. detection by gradually increasing the value of $ and synchronizing many times. First, choose the small- er parameters $ to synchronize ($ $=$ 0.12), then in crease the value of $, and we can complete community detection in the last node coordinates iterative calculation based on the results of change.

Part of the algorithm code is as follows:

input: d $=$ 0, $ $=$ 0.12, count $=$ 1, k

output: Results of dividing network communities

public double[] dYt(int[][] G,double[] v,double $,int count) ${\{}$

Sync6 tong2 $=$ new Sync6();

TongBuSuanFa5 tong5 $=$ new TongBuSuanFa5();

double[][] simaryPoint $=$ tong5.simaryPoint(G);

if(count ${<}=k$ ) ${\{}$

for(int i $=$ 0;i ${<}$ v.length ;i++) ${\{}$

double h $=$ 0;

for(int j=0;j ${<}$ v.length;j++) ${\{}$

// With each node as the active object, determine $ neighborhood the object of each active object

if(Math.abs(v[i]-v[j]) ${<}$ $&&j!=i) ${\{}$

// at present, the point v[j] is in the point v[i] $-neighborhood

double sin=v[j]-v[i]; h+=simaryPoint[i][j]Math.sin(sin);

d++;

${\}}$

${\}}$

// v[i] is the coordinate of the node i

v[i]+=(1.0/dh);

${\}}$

System.out.println("the order" +count+" the iteration: ");

//According to the coordinate value, the clustering of several $-neighborhood closures is found, and

the result of each synchronous division of communities is obtained.

tong2.linyu($, v,G);

//The $ parameter can be changed

$+ $=$ 0.002;

count++;

// the iteration

v=dYt(G, v, $,count);

${\}}$

return v;

${\}}$

The algorithm realizes division of associations by gradually increasing the value of the neighborhood radius. At first, the smaller parameters are selected for synchronization (in the following experiments, $ $=$ 0.12) to form a cluster; Then increase the value $, and on the basis of the result of the change of the coordinate value of the last node, an iterative calculation is performed to complete the community division.
4. Experiment

4.1 The experimental environment

In order to verify the feasibility and effectiveness of the improved algorithm, we do experiment not only in computer-generated graphs [19] but also in real-world graphs. The algorithm is written by Java, and we use MATLAB [20] to draw. All the experiments are completed in the computer with 2.6 GHZ CPU and 4 GB of memory.

4.2 The evaluating indicator

This paper uses two indicators to evaluate the algorithm: modularity and running time.

a)
Modularity [21]: To evaluate the validity and rationality of the divided network community structureï¼ŒNewman et al put forward the concept of modular degree, which is regarded as the evaluation index of division community effect. The formula of modular degree $Q$ is as follows:

$\displaystyle{Q=}\sum^{p}_{i=1}{\left[\frac{e_{i}}{r}-{\left(\frac{d_{i}}{2r}% \right)}^{2}\right]}$ (9)

Where, $r$ is the total number of the network edges, $e_{i}$ is the total number of edges within the community $i$ , $d_{i}$ is the sum of the nodal degrees of all nodes within the community $i$ , the nodal degree is the total number of edges connected to a node in the community. $\\ {(\frac{d_{i}}{2r})}^{2}$ is the expected value of of the proportion of the the randomly connected edges in the same community structure. $Q$ is between 0 and 1. The larger the $Q$ is, the more obvious the network community structuree is and the better the division effect is.
b)
Uptime: An indicator used to evaluate the efficiency of the algorithm. The shorter the running time is, the higher efficiency of the algorithm is.

4.3 Experimental purposes

It compared with module degrees and running time changes of the improved algorithm and the sync algorithm to verify the rationality and effectiveness of the improved algorithm.

4.4 Experimental process of artificial network data set

The experimental steps are as follows:

(1)
It generated GN benchmark network [22] by computer to verify our algorithm. The network consists of 128 nodes and 4 communities, in which each community contains 32 nodes, and the expected value of each nodal degree is 16.
(2)
$z_{in}$ represents the expectations of the nodal degree in the community, and $z_{\textit{out}}$ represents the expectations of nodal degrees outside the community, then $z_{in}+z_{\textit{out}}=$ 16.
(3)
The experiments adopted $\Delta\$=$ 0.003.

4.5 The experimental results and analysis of artificial network data sets

The modularity of the two algorithms is compared as shown in Fig. 7, and the synchronization time comparison is shown in Fig. 8.

Figure 7.

Modularity as a function of $Z_{\textit{out}}$ .

Figure 8.

The running time of the contrast on computer generated graph.

We can see from Fig. 7: The larger the value of $z_{\textit{out}}$ is, the smaller the module degree is and the more fuzzy the community structure is. However, the modular degree of the improved algorithm is always greater than that of the sync algorithm, and the experimental results show that the structure of the improved algorithm is better.

As can be seen from Fig. 8: When the two algorithms synchronize on the same $z_{\textit{out}}$ , the synchronization time of the improved algorithm is shorter, that is the efficiency of the improved algorithm is further improved.

4.6 The experiments and results analysis of real social network data sets

a)
Zachary Club Network [23, 24, 25] is a real social data network set, It’s based on social relations among 34 members of a karate club at a university in the United States. The network consists of 78 edges and 34 nodes. The experimental results of the network is divided into community by using the improved algorithm as shown in Fig. 9.

Table 3
Comparison of experimental results on real network data sets

Datas Nodes Edges $\Delta\$$ Algorithm $Q$ Time cost/s

Sync 0.3900 0.406

Zachary club network 34 78 0.002 Improved algorithm 0.3991 0.351

Sync 0.5945 14.087

The American University Football League network 115 616 0.003 Improved algorithm 0.5983 13.079

Figure 9.
Result acquired by using this algorithm to dividekarate club network.

Zachary karate club network is divided into different communities, and the gap between the experimental results and the real community division results is very small, which proves that the algorithm is reasonable and effective in small networks.
b)
This paper also does an experiment on the American University Football League network. The network was built on the basis of the regular season schedule for 2000 fall season. The network node represents the team, and the side represents the match between the teams, The network consists of 115 nodes and 616 edges. The experimental results of the network is divided into community by using the improved algorithm as shown in Fig. 10.

Figure 10.
Result acquired by using this algorithm to divide NCAA football network.

As you can see from Fig. 10: The community structure that is divided by using this algorithm is very clear, and the effectiveness and feasibility [26, 27] of the improved algorithm are proved in large scale networks .

In order to verify the efficiency of this algorithm we also record the operation frequency and synchronization time of above experiment. Table 3 is the comparison of synchronization steps and time consuming.

From Table 3, we can see that the modularity $Q$ value of the improved algorithm is higher than that of the sync algorithm. It shows that the improved algorithm can divide the community more effectively and reasonably. This is because the improved algorithm is divided into two cases to consider the similarity between nodes. One is that the two nodes were connected directly by the edge. the other is that the two nodes were connected directly by no edge. This method that disconnecting the edges between connected nodes directly and adding secondary nodes .and it has solved the problem of low similarity between the directly connected nodes to make community division more accurate and reasonable.

As we can see from Table 3, the improved algorithm divides communities in less time. This is because the improved algorithm uses the domain radius to divide the network, it replaced clustering order parameters in sync clustering algorithm with $-neighborhood closure and detected the community structure before the object reaches full synchronization. Thus, the number of synchronization between node objects is greatly reduced, and the algorithm efficiency is improved.
5. Conclusion

Datas	Nodes	Edges	$\Delta\$$	Algorithm	$Q$	Time cost/s
				Sync	0.3900	0.406
Zachary club network	34	78	0.002	Improved algorithm	0.3991	0.351
				Sync	0.5945	14.087
The American University Football League network	115	616	0.003	Improved algorithm	0.5983	13.079

Based on the sync clustering algorithm, a new method to measure the similarity between nodes is proposed in this paper. It combined with the concept of neighborhood closure. When the module degree is decreasing, the community division stops, and the result is the community partition result. This method of discovering community structure in advance greatly reduces the time of dynamic interaction between node objects. The experimental results show that it is compared with the original sync clustering algorithm, and the improved algorithm not only improves the running efficiency, but also improves the partition effect. It can be applied to wireless mesh networks. however, when the algorithm is used to divide the community, it has some limitations on the value of neighborhood radius, and the appropriate neighborhood radius can get a better result of the community division. So finding the appropriate parameter value is the focus of the next research.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 11601129), the Key Science and Research Programs in Universities of Henan Province (No. 16A120013), Jiaxing Sci-ence and Technology Project (No. 2012AY1027) and Henan Polytechnic University doctoral fund (No. B2013-035).

References

Lim

and Ryu

, Overlapping community detection using the link-space transformation, IEEE 30th International Conference on Data Engineering (2014), 292–303.

Zhang

W.J.

et al., Overlapping Community detection via link partion of asymmetric weighted graph, IEEE International Conference on Security (2014), 430–435.

Huang

J.B.

et al., Towards online multiresolution community detection in large-scale networks, Plos One 6(8) (2011), 823–829.

Newman

M.E.J.

, Detecting community structure in networks, European Physical Journal B 38(2) (2004), 321–330.

Eustace

Wang

and Gui

, Overlapping community detection using neighborhood ratio matrix, Physica a Statistical Mechanics and its Applications 421 (2015), 510–521.

Zhou

L.Y.

and Zhang

Y.C.

, Predicting miss-ing links via local information, European Physical Journal B 71(4) (2009), 623–630.

Leicht

E.A.

Holme

and Newman

M.E.

, Vertex similarity in networks, Physical Review E Statistical Nonlinear and Soft Matter Physics 73(2) (2006), 261–271.

Pons

and Latapy

, Computing communities in large networks using random walks, in: Proc, In-ternational Symposium on Computer and Information Sciences 2005, pp. 284–293.

Zhang

et al., Hierarchical search result clustering method, Journal of Computer Research and Development 45(3) (2008), 542–547.

10.

Plant

et al., Clustering by synchronization, in: Proc. ACM SIGKDD International Conference on Knowl-edge Discovery and Data Mining, 2010, pp. 583–592.

11.

Huang

et al., A dynamic model based on synchronous network community discovery method, Research and Development of the Computer 49(10) (2012), 2198–2207.

12.

Kuramoto

, Self-entrainment of a population of coupled non-linear oscillators, in: Proc. International Symposium on Mathematical Problems in Theoretical Physics, 1975, pp. 420–422.

13.

Duan

Street

W.N.

Liu

et al., Community detection in graphs through correlation, in: Proc. ACMSIGKDD International Conference on Know Discovery and Data Mining, 2014, pp. 1376–1385.

14.

Zachary

W.W.

, An information flow model for conflict and fission in small groups, Journal of Anthro-Pological Research 33(4) (1977), 452–473.

15.

X.W.

et al., A structural clustering algo-rithm for networks, in: proc. PACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 824–833.

16.

Rezaee

J.A.

and Jasronita

, Parricle swarm optimisation for discrete optimisation problems, Artificial Intelligence Review 43(2) (2015), 243–254.

17.

Chen

Zhang

Cai

et al., A cross-jobs-cross-phases map-reduce scheduling algorithm in heterogeneous cloud, Journal of Computers 28(2) (2017), 145–164.

18.

H.L.

Ning

N.W.

and Niu

L.J.

, Propagation algorithm for community detection based on vertex local influence, Journal of Chinese Computer Systems 38(6) (2017), 1299–1304.

19.

C.L.

Chen

Z.G.

Huang

et al., LPA_LRDC tag propagation community discovery algorithm based on optimized LeaderRank, Journal of Chinese Computer Systems 38(8) (2017),1 746–1750.

20.

Lyu

Zhou

Zhang

Q.M.

et al., The H-index of a network node and its relation to degree and coreness, Nature Communications (2016), 168–178.

21.

J.S.

Liang

and Wang

, Overlapping community detection algorithm based on selection of seed nodes, Application Research of Computers 34(12) (2017), 3534–3537.

22.

Liu

S.C.

Zhu

F.X.

and Lin

, A lable propagation propagation probability based algorithm for overlapping community detection, Chinese Journal of Computers 39(4) (2016), 717–729.

23.

Deng

W.P.

and Yu

F.H.

, Overlapping community detection in complex networks base on multi kernel label propagation, Journal on Communications 38(2) (2017), 53–66.

24.

Liu

Z.J.

et al., An algorithm of wireless network resource allocation in C-RAN, Journal of Computational Methods in Sciences and Engineering (2015), 729–736.

25.

Wen

Z.C.

and He

P.J.

, Network security situation abnormal detection method based on hypothesis test, Journal of Computational Methods in Sciences and Engineering (2016), 505–518.

26.

Wen

Z.C.

and Tang

, Quantitative assessment for network security situation based on weighted factors, Journal of Computational Methods in Sciences and Engineering (2016), 821–833.

27.

Jia

X.Q.

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

An efficient community discovery algorithm based on synchronous dynamic model

Abstract

Keywords

1. Introduction

2. Sync clustering algorithm

3.1 The improved similarity measure

Table 1 The symbols are used in this article

Table 2 Order table of similarity of nodes

4.1 The experimental environment

4.2 The evaluating indicator

4.4 Experimental process of artificial network data set

Footnotes

Acknowledgments

References

Table 1
The symbols are used in this article

Table 2
Order table of similarity of nodes