# A Semantic Community Detection Algorithm Based on Quantizing Progress

Authors: Xu Han; Deyun Chen; Hailu Yang
Journal: Complexity
 (2019)

---

## Abstract

The semantic social network is a kind of network that contains enormous nodes and complex semantic information, and the traditional community detection algorithms could not give the ideal cogent communities instead. To solve the issue of detecting semantic social network, we present a clustering community detection algorithm based on the PSO-LDA model. As the semantic model is LDA model, we use the Gibbs sampling method that can make quantitative parameters map from semantic information to semantic space. Then, we present a PSO strategy with the semantic relation to solve the overlapping community detection. Finally, we establish semantic modularity (SimQ) for evaluating the detected semantic communities. The validity and feasibility of the PSO-LDA model and the semantic modularity are verified by experimental analysis.


---

## Body

## 1. Introduction

With the development of society and the improvement of science and technology, semantic social networks are rapidly developed and many semantic networks, like Twitter and Weibo, have made an insignificant impact in our life so far. In these networks, different individuals have different small social “worlds” which are called communities [1]. Thus, researchers focus attention on community detection not only to divide networks into modules but also to make a deep insight into understanding interesting properties within the semantic social network. In practical application, semantic communities have a great promotion on intelligent information retrieval, marketing management, individual service, and other information management domains [2]. Heretofore, the research on community detection mainly reflects on the following three categories: topological community detection [3], community detection on overlapping construction [4], and semantic community detection.The topological community detection represents the pioneer work, the goal of which is studying the topological constructions and dividing the social networks into several separate networks. The representative algorithms contain Modular Optimization [5], GN [6], and FN [7]. Then, researchers gradually focus on overlapping communities which can be more real than previous research networks. Therefore, CPM [8] was proposed to detect the overlapping communities. Soon afterwards, community detection on overlapping construction received more attention in social networks and many representative algorithms were proposed, including LFM [9], EAGLE [10], COPRA [11], DEMON [12], and so forth. Neuman and Yair [13] proposed an agglomerative spectral clustering method with conductance and edge weights. In their method, the most similar nodes are agglomerated based on eigenvector space and edge weights. But this method only is suitable for the nonsemantic social networks. Then, with the big interest in semantic network, semantic community detection came into researchers’ eyes. Yang and McAuley [14] proposed the CESNA model to develop communities by using edge structure and node attributes. This method leads to more accurate community detection as well as improved robustness in the presence of noise in the network structure. But when this method applies into semantic network, it performs instable. Reihanian and Ali [15] proposed a generic framework for overlapping community detection in social networks with special focus on rating-based social networks. This framework considers the information shared by the users in order to find meaningful communities. The most important feature of semantic communities is that the nodes in these communities not only have topological relationships, but also own semantic context. For the semantic data mining must be considered on the text analysis, and many semantic community detection algorithms applied the Latent Dirichlet Allocation (LDA) [16] model as the core model.In the last few years, the analysis in semantic social network has become popular. Most of these algorithms utilize LDA model as the basic model. The SVM-DTW method proposed by Solera, Calderara, and Cucchiara [17] can work on the hierachical networks. This method makes simple structure and needs less input parameters, but the semantic context is not considered and the detected community has less connection with the real semantic network. Li and Ming and She [18] proposed the GRTM model which not only simulates users’ interests as latent variables through their information, but also considers the connections between users as a result of their information. This method combines the context analysis with topological analysis and the similarity of the detected community is nearly close to the real semantic social network, but it is lack in the feature of sampling that would make some fuzzy irrelevant community. Xiao and Liu [19] proposed the GLDA-FP model which can be extended using the prediscretizing method which can help LDA model detect the topic evolution automatically, but the calculation required is large. As for the LCTA model proposed by Yin, Cao, and Gu [20] which makes the different topic distributions in different communities to make the model reasonable, this method has high accuracy in the result, but the number of communities needs to be preset and some hidden parameters need to be set up with experience.In this paper, we propose a novel community detection algorithm for the objective of dividing nodes into clusters. The main characteristic of communities detected by this algorithm is that members of the same community have common or similar interests. We take into account the topic and keywords information in text from individuals’ words through LDA model, then quantize semantic nodes, and map them into semantic space. Then, we get ideal virtual social communities after using Particle Swarm Optimization algorithm. Last but not least, we build a novel modular model and use the new functionSimQ to evaluate the virtual social communities we make.Compared with other models in semantic social network, such as lovain method model [21] and stochastic block model [22], the LDA model provides the probabilistic method so as to promote the foundation of mathematics. Then considering the following sampling, the Gibbs sampling can give an accurate and powerful mathematical proof for the convergence and solution of the LDA model, which is impossible to happen in the other semantic models. Combined with the PSO algorithm, the probability function compiled by LDA model can be closely integrated with the inertia weight and the constriction factor of the particles [23]. In performance measure, we propose a new module detecting evaluation model based on semantic information using the cosine function, which enriches the classic semantic detecting evaluation model.The rest of the paper is organized as follows: Section2 introduces LDA model in semantic network. Section 3 shows gibbs sampling and the proposed algorithm. In order to verify our approach, we conducted extensive experiments on a real data set. Performance evaluation and experimental results are shown and discussed in Sections 4 and 5. Finally, in Section 6 we make conclusions and envision further work.


## 2. Preliminaries

### 2.1. Community Detection Process

The problem of community detection belongs to NP-hard areas [24] which need initialize solutions at the beginning and optimize solutions constantly in the way of getting the best satisfying solution. The main goal of detecting semantic community is to form communities that individuals share common interests and probably they have similar characteristic [25]. So we show a novel idea that we focus on textual data of individuals’ words. According to the complexity of community detection, we utilize the probabilistic graphical model–LDA to design network. This model has a most clearly hierarchical structure [26], and the scale of parameter spatial has no connection with the number of training documents.First, we select topics and words from individuals’ semantic information through LDA model. Then, we map semantic nodes into semantic space via Gibbs sampling method [27]. Last, in order to get more accurate communities, we use Particle Swarm Optimization (PSO) algorithm to form semantic communities. The proposed community detection algorithm is clearly explained in the following steps.


#### 2.1.1. Similar Semantic Information Discovery

Every individual says different words as each node has its own information contents in semantic social network [28]. So we abstract semantic context into topic, and then we extract keywords from topic. Through semantic information, we convey some distributions to constrain our mess context [29]. In this way, dividing communities in semantic social network based on similar documents, topics, and keywords from social semantic contents make communities real [30]. The LDA probability model is shown in Figure 1.Figure 1
LDA probability model.In this section, we research LDA model on information contents. The relevant mathematical symbols for illustrating the LDA model are given in Table1. LDA model assumes the following generative process for each node:Table 1
The symbol description.
SYMBOL DESCRIPTION N Number of keywords in semantic social network ω Set of keywords in semantic social network,ωi is the i-th keyword in ω d Node set corresponding to keywords setω, di is the i-th node in the semantic social network z Topic set corresponding to keywords setω, zi is the i-th topic in semantic social network θ(di) Topic distribution probability vectorθ over node di φy Keyword distribution probability vector of topicy, φωiy meaning the probability of keyword ωi specific to topic y, φωiy=Pωi∣zi=y α A priori parameter over topic distribution probability specific to each node β A priori parameter over keyword distribution probability specific to a special topic( 1 )  θ~Dirichletα. The parameter θ, which pertains to topic distribution, is subject to the Dirichlet distribution over a priori parameter α.( 2 )  φ~Dirichletβ. The parameter φ, which pertains to keyword distribution, is subject to the Dirichlet distribution over a priori parameter β.( 3 )  zi∣θdi~Multinomialθdi. The topic zi is subject to the multinomial distribution in case of topic distribution probability θdi.( 4 )  ωi∣zi,φzi~Multinominalφzi. The keyword ωi is subject to the multinomial distribution in case of keyword distribution probability φzi over topic zi.The process of forming LDA model is shown in Algorithm1. And M means the number of documents in the process.Algorithm 1:The generative process of LDA.
(1)Extract the keyword distribution, and φ~Dirichletβ; (2)foreach m∈[1,M]do (3)extract N keywords, and N~Poissonφ; (4)Extract topic distribution, and θ~Dirichletα; (5)for each n∈[1,N]do (6)Extract a topic, and this topic obeys zi~Multinomialθdi; (7)Extract a keyword, and this keyword obeys ωi~Multino  min  alφzi; (8)end for (9)end for


## 2.1. Community Detection Process

The problem of community detection belongs to NP-hard areas [24] which need initialize solutions at the beginning and optimize solutions constantly in the way of getting the best satisfying solution. The main goal of detecting semantic community is to form communities that individuals share common interests and probably they have similar characteristic [25]. So we show a novel idea that we focus on textual data of individuals’ words. According to the complexity of community detection, we utilize the probabilistic graphical model–LDA to design network. This model has a most clearly hierarchical structure [26], and the scale of parameter spatial has no connection with the number of training documents.First, we select topics and words from individuals’ semantic information through LDA model. Then, we map semantic nodes into semantic space via Gibbs sampling method [27]. Last, in order to get more accurate communities, we use Particle Swarm Optimization (PSO) algorithm to form semantic communities. The proposed community detection algorithm is clearly explained in the following steps.


### 2.1.1. Similar Semantic Information Discovery

Every individual says different words as each node has its own information contents in semantic social network [28]. So we abstract semantic context into topic, and then we extract keywords from topic. Through semantic information, we convey some distributions to constrain our mess context [29]. In this way, dividing communities in semantic social network based on similar documents, topics, and keywords from social semantic contents make communities real [30]. The LDA probability model is shown in Figure 1.Figure 1
LDA probability model.In this section, we research LDA model on information contents. The relevant mathematical symbols for illustrating the LDA model are given in Table1. LDA model assumes the following generative process for each node:Table 1
The symbol description.
SYMBOL DESCRIPTION N Number of keywords in semantic social network ω Set of keywords in semantic social network,ωi is the i-th keyword in ω d Node set corresponding to keywords setω, di is the i-th node in the semantic social network z Topic set corresponding to keywords setω, zi is the i-th topic in semantic social network θ(di) Topic distribution probability vectorθ over node di φy Keyword distribution probability vector of topicy, φωiy meaning the probability of keyword ωi specific to topic y, φωiy=Pωi∣zi=y α A priori parameter over topic distribution probability specific to each node β A priori parameter over keyword distribution probability specific to a special topic( 1 )  θ~Dirichletα. The parameter θ, which pertains to topic distribution, is subject to the Dirichlet distribution over a priori parameter α.( 2 )  φ~Dirichletβ. The parameter φ, which pertains to keyword distribution, is subject to the Dirichlet distribution over a priori parameter β.( 3 )  zi∣θdi~Multinomialθdi. The topic zi is subject to the multinomial distribution in case of topic distribution probability θdi.( 4 )  ωi∣zi,φzi~Multinominalφzi. The keyword ωi is subject to the multinomial distribution in case of keyword distribution probability φzi over topic zi.The process of forming LDA model is shown in Algorithm1. And M means the number of documents in the process.Algorithm 1:The generative process of LDA.
(1)Extract the keyword distribution, and φ~Dirichletβ; (2)foreach m∈[1,M]do (3)extract N keywords, and N~Poissonφ; (4)Extract topic distribution, and θ~Dirichletα; (5)for each n∈[1,N]do (6)Extract a topic, and this topic obeys zi~Multinomialθdi; (7)Extract a keyword, and this keyword obeys ωi~Multino  min  alφzi; (8)end for (9)end for


## 2.1.1. Similar Semantic Information Discovery

Every individual says different words as each node has its own information contents in semantic social network [28]. So we abstract semantic context into topic, and then we extract keywords from topic. Through semantic information, we convey some distributions to constrain our mess context [29]. In this way, dividing communities in semantic social network based on similar documents, topics, and keywords from social semantic contents make communities real [30]. The LDA probability model is shown in Figure 1.Figure 1
LDA probability model.In this section, we research LDA model on information contents. The relevant mathematical symbols for illustrating the LDA model are given in Table1. LDA model assumes the following generative process for each node:Table 1
The symbol description.
SYMBOL DESCRIPTION N Number of keywords in semantic social network ω Set of keywords in semantic social network,ωi is the i-th keyword in ω d Node set corresponding to keywords setω, di is the i-th node in the semantic social network z Topic set corresponding to keywords setω, zi is the i-th topic in semantic social network θ(di) Topic distribution probability vectorθ over node di φy Keyword distribution probability vector of topicy, φωiy meaning the probability of keyword ωi specific to topic y, φωiy=Pωi∣zi=y α A priori parameter over topic distribution probability specific to each node β A priori parameter over keyword distribution probability specific to a special topic( 1 )  θ~Dirichletα. The parameter θ, which pertains to topic distribution, is subject to the Dirichlet distribution over a priori parameter α.( 2 )  φ~Dirichletβ. The parameter φ, which pertains to keyword distribution, is subject to the Dirichlet distribution over a priori parameter β.( 3 )  zi∣θdi~Multinomialθdi. The topic zi is subject to the multinomial distribution in case of topic distribution probability θdi.( 4 )  ωi∣zi,φzi~Multinominalφzi. The keyword ωi is subject to the multinomial distribution in case of keyword distribution probability φzi over topic zi.The process of forming LDA model is shown in Algorithm1. And M means the number of documents in the process.Algorithm 1:The generative process of LDA.
(1)Extract the keyword distribution, and φ~Dirichletβ; (2)foreach m∈[1,M]do (3)extract N keywords, and N~Poissonφ; (4)Extract topic distribution, and θ~Dirichletα; (5)for each n∈[1,N]do (6)Extract a topic, and this topic obeys zi~Multinomialθdi; (7)Extract a keyword, and this keyword obeys ωi~Multino  min  alφzi; (8)end for (9)end for


## 3. Gibbs Sampling and PSO Strategy

### 3.1. Gibbs Sampling

Gibbs sampling [31] is a simple case of Markov-chain Monte Carlo (MCMC) [32] and aims at extracting a set of approximate samples from Markov-chain that is targeted to make a suitable probability distribution for converging to optimal solutions in high-dimensional models [33] such as LDA. According to the feature of Markov-chain, the probability-distribution function becomes the key to Gibbs sampling [34]. As for LDA in this text, we only sample topics in semantic social network; that is, we only need to consider hidden variety zi. We denote z¬i (topic set besides zi) and ω¬i (set of keywords besides ωi) to draw a posterior probability Pzi=y∣z¬i,ωi. As for i, we can find the corresponding keyword ωi. So the probability can be described as in the following equation.(1)Pzi=y∣z¬i,ωi∝Pzi=y,ωi=t∣ω¬i,z¬iWhen zi=y and ωi=t (t is one of the keywords in ω; y, which corresponds to t, is one of the topics in z), the probability Pzi=y,ωi=t∣ω¬i,z¬i only involves conjugate distribution of d-th the document and k-th topic under the Dirichlet-multinomial model.We makenpk as the number of k-th topics in d-th document, and the multinomial distribution can be described as(2)np=np1,np2,…npK The number of m-th keywords in k-th topic, named nqm, can be shown as follows under multinomial distribution.(3)nq=nq1,nq2,…nqM The posterior distribution of θdi and φzi can be obtained in the following equations.(4)Pθdi∣ω¬i,z¬i=Dirchletθdi∣np,¬i+α(5)Pφzi∣ω¬i,z¬i=Dirichletφzi∣nq,¬i+βnp,¬i is the number of topics and nq,¬i is the number of keywords.The distribution probabilityPzi=y,ωi=t∣ω¬i,z¬i can be calculated by (6)~(11).(6)Pzi=y,ωi=t∣ω¬i,z¬i=∫Pzi=y,ωi=t,φzi,θdi∣ω¬i,z¬idθdidφzi(7)=∫Pzi=y,θdi∣ω¬i,z¬iPωi=t,φzi∣ω¬i,z¬idθdidφzi(8)=∫Pzi=y∣θdiDirchletθdi∣np,¬i+αdθdi(9)•∫Pωi=t∣φziDirichletφzi∣nq,¬i+βdφzi(10)=np,¬iy+α∑f=1Knp,¬if+αnq,¬it+β∑g=1Vnq,¬ig+β(11)⇒Pzi=y∣z¬i,ωi∝np,¬iy+α∑f=1Knp,¬if+αnq,¬it+β∑g=1Vnq,¬ig+βnp,¬iy is the amount of topics while zi=y, ∑f=1Knp,¬if is the amount of topics, nq,¬it is the amount of keywords while ωi=t, and ∑g=1Vnq,¬ig is the amount of keywords.


### 3.2. PSO Class Dependent LDA (PSO-LDA)

Particle Swarm Optimization (PSO) is an intelligent optimization algorithm. It was first proposed by J.Kennedy and R.C.Eberhart [35]. PSO algorithm has the advantages of simplified, rather quick convergence [36] speed and less controlling parameter, and so forth.Compared with other optimization algorithms, such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Simulate Anneal (SA), PSO algorithm has two attractive features: firstly, PSO optimizes the solution from the local optimum first and runs fast, which makes the algorithm more adaptable to the evolution of networks; secondly, particles in PSO can be mapped to nodes in semantic network; the process of finding the optimal solution in PSO is consistent with the birth process of the semantic community.PSO puts a set of random solutions at system startup time and uses iterative search to find out optimal solutions [37]. In PSO, a solution of each optimization problem is called “particle”. Each particle owns fitness value of itself. So we design a heuristic method to detect communities based on PSO. Each particle searches for the optimal solution by sharing social information between individuals.In PSO-LDA, some LDA semantic feature is put into PSO. We use nodes in semantic social network mapping to “particle” in PSO and utilize semantic information vector of each node mapping to velocity of each particle in PSO. As for fitness value, we use information similar function instead. In PSO, we normalize that the nodes in semantic social network simulate the behavior of a “bird flock”, where social sharing of information takes place, individuals’ gains from the discoveries and previous experience of all other nodes during the search for food [38]. Thus, each node, called particle, in semantic social network which is called swarm, is assumed to “fly” over the search place looking for promising regions on the landscape.First, we assume the search place isD-dimension space; and the i-th particle position of the swarm is denoted as D-dimension, the vector Wi=wi1,wi2,⋯,wid,⋯,wiD. Each particle has two pieces of message in the process: its “best” position with the smallest value (i.e., its personal best position) Pi=pi1,pi2,⋯,pid,⋯,piD and the best function value of global particles in swarm (i.e., the global best position of all particles) Pg=pg1,pg2,⋯,pgd,⋯,pgD. At each iteration, i-th particle of the swarm updates its position and the velocity Vi=vi1,vi2,⋯,vid,⋯,viD according to the following equation:(12)vids+1=ηvids+λ1r1spids-wids+λ2r2spgds-widss is the current iteration, j∈1,2,⋯,D, i∈1,2,⋯,N, N represents the size of population, D is the dimension of the search place, η is the inertia weight, and λ1 and λ2 are two positive constants. r1 and r2 are study factors, that is, two random numbers extracted from the range 0,1 for each dimension.In the search place, once velocityvids+1 updated, the i-th particle position wid is changed as in the following equation.(13)wids+1=wids+ξvids+1ξ is a constriction factor which manages and regulates the velocity’s magnitude to maintain a balance between exploration and exploitation and it can be calculated as follows:(14)ξ=22-λ-λ2-4λλ=λ1+λ2, λ>4. The constriction factor has influence on the proposed algorithm; we discuss the issue in part 4. The pseudocode for PSO is described in Algorithm 2 [39].Algorithm 2:Optimization algorithm by PSO.
Input: The semantic social network gragh disposed by LDA; Output: Useful transformable probability matrix; Step  0. Initialize proper parameters, inertia weight η=0.632, constriction factor ξ=0.729, study factors r1=2.8, r2=1.3, population size(the size of network) M=200, particle size (the number of nodes in semantic social network) N=1000 and maximum iteration MI=200. Step  1. Initialize all particles and let s=0; Step  2. Evaluate fitness of each particle; Step  3. Judge whether the ultimate criteria is satisfied. If s>MI, stop and jump to Final.; otherwise refresh variables according to the following steps; Step  4. Refresh pid by comparing the current fitness of each particle with its own historical best position p i d, if pid gets smaller, then change it with the current position; Step  5. Refresh pgd by comparing the current best fitness of all particles with the historical best position pgd of the whole swarm, if pgd gets smaller, then change it with the current best position; Step  6. Refresh vids+1 and wids+1 using Eq (12) and Eq (13); Step  7. s=s+1, return Step2; Final.


## 3.1. Gibbs Sampling

Gibbs sampling [31] is a simple case of Markov-chain Monte Carlo (MCMC) [32] and aims at extracting a set of approximate samples from Markov-chain that is targeted to make a suitable probability distribution for converging to optimal solutions in high-dimensional models [33] such as LDA. According to the feature of Markov-chain, the probability-distribution function becomes the key to Gibbs sampling [34]. As for LDA in this text, we only sample topics in semantic social network; that is, we only need to consider hidden variety zi. We denote z¬i (topic set besides zi) and ω¬i (set of keywords besides ωi) to draw a posterior probability Pzi=y∣z¬i,ωi. As for i, we can find the corresponding keyword ωi. So the probability can be described as in the following equation.(1)Pzi=y∣z¬i,ωi∝Pzi=y,ωi=t∣ω¬i,z¬iWhen zi=y and ωi=t (t is one of the keywords in ω; y, which corresponds to t, is one of the topics in z), the probability Pzi=y,ωi=t∣ω¬i,z¬i only involves conjugate distribution of d-th the document and k-th topic under the Dirichlet-multinomial model.We makenpk as the number of k-th topics in d-th document, and the multinomial distribution can be described as(2)np=np1,np2,…npK The number of m-th keywords in k-th topic, named nqm, can be shown as follows under multinomial distribution.(3)nq=nq1,nq2,…nqM The posterior distribution of θdi and φzi can be obtained in the following equations.(4)Pθdi∣ω¬i,z¬i=Dirchletθdi∣np,¬i+α(5)Pφzi∣ω¬i,z¬i=Dirichletφzi∣nq,¬i+βnp,¬i is the number of topics and nq,¬i is the number of keywords.The distribution probabilityPzi=y,ωi=t∣ω¬i,z¬i can be calculated by (6)~(11).(6)Pzi=y,ωi=t∣ω¬i,z¬i=∫Pzi=y,ωi=t,φzi,θdi∣ω¬i,z¬idθdidφzi(7)=∫Pzi=y,θdi∣ω¬i,z¬iPωi=t,φzi∣ω¬i,z¬idθdidφzi(8)=∫Pzi=y∣θdiDirchletθdi∣np,¬i+αdθdi(9)•∫Pωi=t∣φziDirichletφzi∣nq,¬i+βdφzi(10)=np,¬iy+α∑f=1Knp,¬if+αnq,¬it+β∑g=1Vnq,¬ig+β(11)⇒Pzi=y∣z¬i,ωi∝np,¬iy+α∑f=1Knp,¬if+αnq,¬it+β∑g=1Vnq,¬ig+βnp,¬iy is the amount of topics while zi=y, ∑f=1Knp,¬if is the amount of topics, nq,¬it is the amount of keywords while ωi=t, and ∑g=1Vnq,¬ig is the amount of keywords.


## 3.2. PSO Class Dependent LDA (PSO-LDA)

Particle Swarm Optimization (PSO) is an intelligent optimization algorithm. It was first proposed by J.Kennedy and R.C.Eberhart [35]. PSO algorithm has the advantages of simplified, rather quick convergence [36] speed and less controlling parameter, and so forth.Compared with other optimization algorithms, such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Simulate Anneal (SA), PSO algorithm has two attractive features: firstly, PSO optimizes the solution from the local optimum first and runs fast, which makes the algorithm more adaptable to the evolution of networks; secondly, particles in PSO can be mapped to nodes in semantic network; the process of finding the optimal solution in PSO is consistent with the birth process of the semantic community.PSO puts a set of random solutions at system startup time and uses iterative search to find out optimal solutions [37]. In PSO, a solution of each optimization problem is called “particle”. Each particle owns fitness value of itself. So we design a heuristic method to detect communities based on PSO. Each particle searches for the optimal solution by sharing social information between individuals.In PSO-LDA, some LDA semantic feature is put into PSO. We use nodes in semantic social network mapping to “particle” in PSO and utilize semantic information vector of each node mapping to velocity of each particle in PSO. As for fitness value, we use information similar function instead. In PSO, we normalize that the nodes in semantic social network simulate the behavior of a “bird flock”, where social sharing of information takes place, individuals’ gains from the discoveries and previous experience of all other nodes during the search for food [38]. Thus, each node, called particle, in semantic social network which is called swarm, is assumed to “fly” over the search place looking for promising regions on the landscape.First, we assume the search place isD-dimension space; and the i-th particle position of the swarm is denoted as D-dimension, the vector Wi=wi1,wi2,⋯,wid,⋯,wiD. Each particle has two pieces of message in the process: its “best” position with the smallest value (i.e., its personal best position) Pi=pi1,pi2,⋯,pid,⋯,piD and the best function value of global particles in swarm (i.e., the global best position of all particles) Pg=pg1,pg2,⋯,pgd,⋯,pgD. At each iteration, i-th particle of the swarm updates its position and the velocity Vi=vi1,vi2,⋯,vid,⋯,viD according to the following equation:(12)vids+1=ηvids+λ1r1spids-wids+λ2r2spgds-widss is the current iteration, j∈1,2,⋯,D, i∈1,2,⋯,N, N represents the size of population, D is the dimension of the search place, η is the inertia weight, and λ1 and λ2 are two positive constants. r1 and r2 are study factors, that is, two random numbers extracted from the range 0,1 for each dimension.In the search place, once velocityvids+1 updated, the i-th particle position wid is changed as in the following equation.(13)wids+1=wids+ξvids+1ξ is a constriction factor which manages and regulates the velocity’s magnitude to maintain a balance between exploration and exploitation and it can be calculated as follows:(14)ξ=22-λ-λ2-4λλ=λ1+λ2, λ>4. The constriction factor has influence on the proposed algorithm; we discuss the issue in part 4. The pseudocode for PSO is described in Algorithm 2 [39].Algorithm 2:Optimization algorithm by PSO.
Input: The semantic social network gragh disposed by LDA; Output: Useful transformable probability matrix; Step  0. Initialize proper parameters, inertia weight η=0.632, constriction factor ξ=0.729, study factors r1=2.8, r2=1.3, population size(the size of network) M=200, particle size (the number of nodes in semantic social network) N=1000 and maximum iteration MI=200. Step  1. Initialize all particles and let s=0; Step  2. Evaluate fitness of each particle; Step  3. Judge whether the ultimate criteria is satisfied. If s>MI, stop and jump to Final.; otherwise refresh variables according to the following steps; Step  4. Refresh pid by comparing the current fitness of each particle with its own historical best position p i d, if pid gets smaller, then change it with the current position; Step  5. Refresh pgd by comparing the current best fitness of all particles with the historical best position pgd of the whole swarm, if pgd gets smaller, then change it with the current best position; Step  6. Refresh vids+1 and wids+1 using Eq (12) and Eq (13); Step  7. s=s+1, return Step2; Final.


## 4. Performance Measure

Generally speaking, the performance measure of semantic social network is mostly based on the topological construction. And theEQ model proposed by Shen et al. [40] is widely used in evaluating overlapping communities, which is described in the following equation:(15)EQ=1R∑i∑v∈Ci,w∈Ci1OvOwAvw-kvkwRkv is the degree of node v and kw is the degree of node w, R=∑vwAvw is the total degree of the network, Avw is the element of adjacency matrix of the network, Ov is the number of communities which the node v belongs to and Ow is the number of communities which the node w belongs to, and Ci is the i-th community in the network. For we use both topological construction and semantic context to detect communities, a novel evaluation model named SimQ, which we add information similarity into topological evaluation index, is given by the following equation.(16)SimQ=1R1∑i,j∑di∈Ci,dj∈CjSimdi,djOdiOdjAdidj-kdikdjR1di is the i-th node and dj is the j-th node, Odi is the number of communities that the node di pertains and Odj is the number of communities that the node dj pertains, R1=∑didjAdidj is the total degree of the network, Adidj is the element of adjacency matrix of the network, and the range of value for SimQ is 0,1. As for the information similarity Simdi,dj, we give a normal social graph G=D,E,Xdi/djK,Simdi,dj, where D is a set of nodes in the network and di/dj is the i/j-th node; E is the set of edges linking to graph nodes. The actual point of Simdi,dj is to measure the structural correlation of nodes and add semantic correlation components at the same time. This is more suitable for the basic characteristics of the semantic communities. Each node di has connection with an information vector XdiK=x1i,x2i,…,xni; Simdi,dj is the information similarity of two neighbor nodes i and j which is calculated as(17)Simdi,dj=∑i,j=1nXdiKXdjK∑i=1nXdiK2∑j=1nXdjK2K is the dimension of the social network. In our method, if the semantic components of two nodes are close, the projection angles of these two nodes in two-dimensional space will be relatively small. On the contrary, the projection vectors are in contradictory situation.


## 5. Experimental Results

In this part, we would present and discuss the experiments with topics number analysis, evaluation criterion, real datasets, and different community detection algorithms, based on three datasets (the American College Football network dataset, the Krebs polbooks network dataset, and the dolphins network dataset).


### 5.1. The Analysis on Topics Number

The number of topicsT, which is one of the input parameters in PSO-LDA model, can influence the compactedness of communities. So we choose the following three datasets to verify the effect of topics T over the result: (1) The American College Football network is shown in Figure 2. This network, created by Newman, is a complex social network about American College Football league. Nodes are regarded as football teams and one edge, between two neighbor nodes, represents that two football teams have played a match. It contains 115 nodes and 616 edges. (2) The Krebs polbooks network established by V.Kreb is shown in Figure 3. The nodes represent the politics books sold on Amazon. Generally, the books on political tendency are approximately divided into three classes. So in order to get topic distribution, Newman collected the political tendency in 3 steps away around each node. (3) The dolphins network collected by Newman is shown in Figure 4. The dolphins network is made up of two families, including 62 nodes and 159 edges. We simulate each node with the semantic information to fit on Dirichlet distribution.Figure 2
The graph of football network.Figure 3
The graph of polbooks network.Figure 4
The dolphins network.In this section, we use the topic number to experimentalize on three datasets (football, polbooks, and dolphins). Figure5 shows the comparison of EQ and SimQ on the three datasets with T=1,2,⋯,20. While the topic number T grows bigger and the topic distribution rises higher, the number of detected communities gets bigger as T rises. In Figure 5, when the topic number gets larger to a certain degree, the topic distribution tends to be stable, resulting in the increment of communities. From the comparison of EQ and SimQ, these two performance measure models tend to decrease as T increases, since the topic number T arrives at an optimal point. The optimal value of T is 6 in Figure 5.Figure 5
The performance of detected communities withT.For the sake of getting communities more intuitive, Figure6 shows the detected communities of three datasets when T is 6, 12, and 18.Figure 6
The communities forT=6,12,18 (the black nodes are overlapping nodes).
(a) (b) (c)


### 5.2. The Comparison on Different Optimization Algorithms

In this section, we do the comparison on different optimization algorithms with three network datasets above (dolphins, polbooks, and football). We compare the number of communities, the size of communities, runtime, and semantic concentration with PSO algorithm, Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Simulate Anneal (SA). The result is shown in Figure7. From Figure 7, we can see PSO algorithm makes more numbers of communities and smaller size of communities than others. As for runtime in PSO algorithm, it runs a little better than ACO and SA. The semantic concentration (SC) [41] is a function for measuring and testing degree of coagulation on specific topic and SC is shown in the following equation:(18)SC=∑ijSimdi,dj·δij∑ijSimdi,djδij is the performance measure of communities links, while δij=1 and only if i and j belong to the same community, there is a link between i and j. Compared with similarity function SimQ, SC makes focus on the stability of social groups in local environment. But what needs to be noted is that higher SimQ does not mean higher SC in communities and higher SC does not mean we can get the best divisions; this is because the overlapping part of communities can effect the semantic cohesion. So the ideal community construction should be suitable with SimQ and SC, and this also fits the performance measure of overall optimization and local optimization. Compared with GA, ACO, and SA in Figure 7, the detected communities by PSO have a little small size and a bit more community numbers, which is in accordance with the topic distribution. As for runtime, PSO runs a bit slower than ACO but much better than GA and SA. Figure 8 shows four optimization algorithms run on dolphins network, and as similar as Figure 7, PSO works much better than other algorithms on community detection.Figure 7
The performance of different optimization algorithms.Figure 8
The comparison on different optimization algorithms on dolphins (the black nodes are overlapping nodes).
(a)
PSO (b)
GA (c)
ACO (d)
SA


### 5.3. The Comparison on the Constriction Factor withEQ and SimQ

In this section, we compareEQ and SimQ over three datasets. The run diagrams, which EQ and SimQ run in three datasets, are shown in Figure 9. From (16), we put the similar function of information Simdi,dj into SimQ and Simdi,dj<1. So generally, the tendency of EQ diagram can be higher than SimQ. The maximum value of EQ in football dataset is 0.4233 (ξ =0.52) and SimQ is 0.4064 (ξ=0.53); and there exists bias when ξ =0.53, and the value of EQ is 0.4112 (not the maximum one). There is also bias in polbooks dataset and dolphins dataset, and the maximum value of EQ is 0.4154 (ξ =0.54) and SimQ is 0.3982 (ξ =0.55) in polbooks dataset while the maximum value of EQ is 0.4639 (ξ =0.60) and SimQ is 0.4489 (ξ =0.62) in dolphins dataset.Figure 9
The digrams of comparison on the constriction factor withEQ and SimQ.


### 5.4. The Comparison on Community Detection Algorithms

Considering the bias in the semantic community detection, we utilize classical nonsemantic algorithms to illuminate the issue with the football dataset, for example.We choose GN, FN, LFM, COPRA as nonsemantic classical algorithms, where LFM and COPRA are the overlapping community detection algorithms. TheEQ and SimQ of the algorithms above are covered in Table 2 and the detection of communities is shown in Figure 10 with football dataset.Table 2
The classical nonsemantic algorithms onEQ, SimQ, and SC.
Algorithms E Q S i m Q S C GN 0.4615 0.3573 0.3873 FN 0.4061 0.3174 0.4012 LFM 0.3255 0.2331 0.3625 COPRA 0.5407 0.4115 0.3902 PSO-LDA 0.5132 0.4258 0.4842Figure 10
The detected communities with nonclassical algorithms on football.
(a)
GN (b)
FN (c)
LFM (d)
COPRAFrom the result in Table2, the EQ of nonsemantic classical algorithms work higher than that of PSO-LDA (0.5132), but the SimQ works lower than PSO-LDA (0.4258). So it suggests that the nonsemantic classical algorithms make a higher EQ in the topological construction detection and a lower SimQ in the semantic detection. There is a bias in community detection by nonsemantic classical algorithms compared to semantic algorithms in the way of getting the ideal communities. On the one hand, we verify the performance of these algorithms; on the other hand, we use this experiment to verify the relation above EQ, SimQ, and SC. As for SC in Table 2, PSO-LDA performs better in SimQ and has high EQ, and PSO-LDA is higher than other algorithms in SC. This means PSO-LDA performs well in overall search (EQ and SimQ) and works better than others in local search (SC).


### 5.5. The Comparison on Real Datasets

In this section, we compare real different datasets, including Quantifying Link Semantics-Publication (QLSP) dataset (805 nodes), Academic Social Network (ASN) dataset (extract 2500 nodes) (https://www.aminer.cn/aminernetwork), extracting 10000 nodes and 20000 nodes from DBLP (December 31, 2014) dataset (2839219 nodes) (http://dblp.uni-trier.de/db/) as DBLP(A) and DBLP(B), and Enron email network (Enron) dataset (extract 25000 nodes) (http://snap.stanford.edu/data/email-Enron.html). The EQ, SimQ, and NC(the number of detected communities) of datasets above detected by various algorithms are reported in Table 3, as the PSO-LDA for T=6. The histogram of EQ is shown in Figure 11 and SimQ in Figure 12. From Figures 11 and 12, the PSO-LDA model can be more suitable to solve the semantic community detection than the classical nonsemantic algorithms.Table 3
The results of classical nonsemantic algorithms under various datasets.
Algorithms E Q / S i m Q / N C QLSP ASN DBLP(A) DBLP(B) Enron GN E Q 0.3107 0.2103 0.2822 0.3193 0.3256 S i m Q 0.2309 0.2054 0.2137 0.2863 0.2874 N C 10 35 17 16 27 FN E Q 0.4215 0.2234 0.3191 0.2618 0.3475 S i m Q 0.3134 0.1711 0.2912 0.2561 0.2994 N C 10 33 19 16 26 LFM E Q 0.3668 0.2403 0.4052 0.3613 0.4153 S i m Q 0.3167 0.2172 0.3317 0.3121 0.3572 N C 12 29 21 12 30 COPRA E Q 0.4196 0.1213 0.383 0.4112 0.4559 S i m Q 0.2891 0.1124 0.2971 0.3217 0.4007 N C 13 31 21 13 26 PSO-LDA E Q 0.3248 0.2112 0.3537 0.2998 0.3401 S i m Q 0.3412 0.2734 0.3641 0.3569 0.3989 N C 14 30 23 15 27Figure 11
The histogram ofEQ with various classical algorithms.Figure 12
The histogram ofSimQ with various classical algorithms.


## 5.1. The Analysis on Topics Number

The number of topicsT, which is one of the input parameters in PSO-LDA model, can influence the compactedness of communities. So we choose the following three datasets to verify the effect of topics T over the result: (1) The American College Football network is shown in Figure 2. This network, created by Newman, is a complex social network about American College Football league. Nodes are regarded as football teams and one edge, between two neighbor nodes, represents that two football teams have played a match. It contains 115 nodes and 616 edges. (2) The Krebs polbooks network established by V.Kreb is shown in Figure 3. The nodes represent the politics books sold on Amazon. Generally, the books on political tendency are approximately divided into three classes. So in order to get topic distribution, Newman collected the political tendency in 3 steps away around each node. (3) The dolphins network collected by Newman is shown in Figure 4. The dolphins network is made up of two families, including 62 nodes and 159 edges. We simulate each node with the semantic information to fit on Dirichlet distribution.Figure 2
The graph of football network.Figure 3
The graph of polbooks network.Figure 4
The dolphins network.In this section, we use the topic number to experimentalize on three datasets (football, polbooks, and dolphins). Figure5 shows the comparison of EQ and SimQ on the three datasets with T=1,2,⋯,20. While the topic number T grows bigger and the topic distribution rises higher, the number of detected communities gets bigger as T rises. In Figure 5, when the topic number gets larger to a certain degree, the topic distribution tends to be stable, resulting in the increment of communities. From the comparison of EQ and SimQ, these two performance measure models tend to decrease as T increases, since the topic number T arrives at an optimal point. The optimal value of T is 6 in Figure 5.Figure 5
The performance of detected communities withT.For the sake of getting communities more intuitive, Figure6 shows the detected communities of three datasets when T is 6, 12, and 18.Figure 6
The communities forT=6,12,18 (the black nodes are overlapping nodes).
(a) (b) (c)


## 5.2. The Comparison on Different Optimization Algorithms

In this section, we do the comparison on different optimization algorithms with three network datasets above (dolphins, polbooks, and football). We compare the number of communities, the size of communities, runtime, and semantic concentration with PSO algorithm, Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Simulate Anneal (SA). The result is shown in Figure7. From Figure 7, we can see PSO algorithm makes more numbers of communities and smaller size of communities than others. As for runtime in PSO algorithm, it runs a little better than ACO and SA. The semantic concentration (SC) [41] is a function for measuring and testing degree of coagulation on specific topic and SC is shown in the following equation:(18)SC=∑ijSimdi,dj·δij∑ijSimdi,djδij is the performance measure of communities links, while δij=1 and only if i and j belong to the same community, there is a link between i and j. Compared with similarity function SimQ, SC makes focus on the stability of social groups in local environment. But what needs to be noted is that higher SimQ does not mean higher SC in communities and higher SC does not mean we can get the best divisions; this is because the overlapping part of communities can effect the semantic cohesion. So the ideal community construction should be suitable with SimQ and SC, and this also fits the performance measure of overall optimization and local optimization. Compared with GA, ACO, and SA in Figure 7, the detected communities by PSO have a little small size and a bit more community numbers, which is in accordance with the topic distribution. As for runtime, PSO runs a bit slower than ACO but much better than GA and SA. Figure 8 shows four optimization algorithms run on dolphins network, and as similar as Figure 7, PSO works much better than other algorithms on community detection.Figure 7
The performance of different optimization algorithms.Figure 8
The comparison on different optimization algorithms on dolphins (the black nodes are overlapping nodes).
(a)
PSO (b)
GA (c)
ACO (d)
SA


## 5.3. The Comparison on the Constriction Factor withEQ and SimQ

In this section, we compareEQ and SimQ over three datasets. The run diagrams, which EQ and SimQ run in three datasets, are shown in Figure 9. From (16), we put the similar function of information Simdi,dj into SimQ and Simdi,dj<1. So generally, the tendency of EQ diagram can be higher than SimQ. The maximum value of EQ in football dataset is 0.4233 (ξ =0.52) and SimQ is 0.4064 (ξ=0.53); and there exists bias when ξ =0.53, and the value of EQ is 0.4112 (not the maximum one). There is also bias in polbooks dataset and dolphins dataset, and the maximum value of EQ is 0.4154 (ξ =0.54) and SimQ is 0.3982 (ξ =0.55) in polbooks dataset while the maximum value of EQ is 0.4639 (ξ =0.60) and SimQ is 0.4489 (ξ =0.62) in dolphins dataset.Figure 9
The digrams of comparison on the constriction factor withEQ and SimQ.


## 5.4. The Comparison on Community Detection Algorithms

Considering the bias in the semantic community detection, we utilize classical nonsemantic algorithms to illuminate the issue with the football dataset, for example.We choose GN, FN, LFM, COPRA as nonsemantic classical algorithms, where LFM and COPRA are the overlapping community detection algorithms. TheEQ and SimQ of the algorithms above are covered in Table 2 and the detection of communities is shown in Figure 10 with football dataset.Table 2
The classical nonsemantic algorithms onEQ, SimQ, and SC.
Algorithms E Q S i m Q S C GN 0.4615 0.3573 0.3873 FN 0.4061 0.3174 0.4012 LFM 0.3255 0.2331 0.3625 COPRA 0.5407 0.4115 0.3902 PSO-LDA 0.5132 0.4258 0.4842Figure 10
The detected communities with nonclassical algorithms on football.
(a)
GN (b)
FN (c)
LFM (d)
COPRAFrom the result in Table2, the EQ of nonsemantic classical algorithms work higher than that of PSO-LDA (0.5132), but the SimQ works lower than PSO-LDA (0.4258). So it suggests that the nonsemantic classical algorithms make a higher EQ in the topological construction detection and a lower SimQ in the semantic detection. There is a bias in community detection by nonsemantic classical algorithms compared to semantic algorithms in the way of getting the ideal communities. On the one hand, we verify the performance of these algorithms; on the other hand, we use this experiment to verify the relation above EQ, SimQ, and SC. As for SC in Table 2, PSO-LDA performs better in SimQ and has high EQ, and PSO-LDA is higher than other algorithms in SC. This means PSO-LDA performs well in overall search (EQ and SimQ) and works better than others in local search (SC).


## 5.5. The Comparison on Real Datasets

In this section, we compare real different datasets, including Quantifying Link Semantics-Publication (QLSP) dataset (805 nodes), Academic Social Network (ASN) dataset (extract 2500 nodes) (https://www.aminer.cn/aminernetwork), extracting 10000 nodes and 20000 nodes from DBLP (December 31, 2014) dataset (2839219 nodes) (http://dblp.uni-trier.de/db/) as DBLP(A) and DBLP(B), and Enron email network (Enron) dataset (extract 25000 nodes) (http://snap.stanford.edu/data/email-Enron.html). The EQ, SimQ, and NC(the number of detected communities) of datasets above detected by various algorithms are reported in Table 3, as the PSO-LDA for T=6. The histogram of EQ is shown in Figure 11 and SimQ in Figure 12. From Figures 11 and 12, the PSO-LDA model can be more suitable to solve the semantic community detection than the classical nonsemantic algorithms.Table 3
The results of classical nonsemantic algorithms under various datasets.
Algorithms E Q / S i m Q / N C QLSP ASN DBLP(A) DBLP(B) Enron GN E Q 0.3107 0.2103 0.2822 0.3193 0.3256 S i m Q 0.2309 0.2054 0.2137 0.2863 0.2874 N C 10 35 17 16 27 FN E Q 0.4215 0.2234 0.3191 0.2618 0.3475 S i m Q 0.3134 0.1711 0.2912 0.2561 0.2994 N C 10 33 19 16 26 LFM E Q 0.3668 0.2403 0.4052 0.3613 0.4153 S i m Q 0.3167 0.2172 0.3317 0.3121 0.3572 N C 12 29 21 12 30 COPRA E Q 0.4196 0.1213 0.383 0.4112 0.4559 S i m Q 0.2891 0.1124 0.2971 0.3217 0.4007 N C 13 31 21 13 26 PSO-LDA E Q 0.3248 0.2112 0.3537 0.2998 0.3401 S i m Q 0.3412 0.2734 0.3641 0.3569 0.3989 N C 14 30 23 15 27Figure 11
The histogram ofEQ with various classical algorithms.Figure 12
The histogram ofSimQ with various classical algorithms.


## 6. Conclusion

In this paper, we presented a novel community detection algorithm PSO-LDA that combines the topological construction with semantic information. It can avoid the number and the size of communities. For the Gibbs sampling solving the hidden parameter in the proposed model, the sampling result approaches to the realistic state. The main contribution of this research focuses on how to use different similarity measure to measure similarity between nodes based on topological construction and their semantic information. As for future work, we would apply the model in some fields such as privacy protection and worm containment in semantic social network.



---

*Source: 3475458-2019-01-09.xml*