LBLP: Link-Clustering-Based Approach for Overlapping Community Detection

We assume that a social network $G=(V,E)$ contains the vertex set $V$ and the edge set $E$ . Each vertex in $V$ represents as an actor and an edge in $E$ represents the interaction between the actors.

Problem Given a network including the node set $V=\{v_1,v_2,\mathrm{\cdots },v_m\}$ , divide the edge set $E=\{e_1,e_2,\mathrm{\cdots },e_n\}$ , which is defined for the edges between the different nodes, into $k$ communities $P_1,P_2,\mathrm{\cdots },P_k$ on the basis of the link behavior and determine the node community $C_i$ induced by the edge community $P_i$ .

Definition 1 Line graph Give a network $G=(V,E)$ , create a line graph LG of the original network. The nodes in LG are the edges in $G$ and the edges in LG exist on the basis of whether the edges share common nodes in $G$ , i.e., $V(\mathrm{LG})=E(G)$ .

Definition 2 Edge weight Given $\epsilon \in E(G)$ , $\mathrm{End}(\epsilon )$ represents the nodes connecting the edge $\epsilon$ . For all the edge pairs $({\epsilon }_i,{\epsilon }_j)$ , and ${\epsilon }_i\ne {\epsilon }_j$ , $E(\mathrm{LG})=\{({\epsilon }_i,{\epsilon }_j)|\mathrm{End}({\epsilon }_i)\cap \mathrm{End}({\epsilon }_j)=\mathrm{\varnothing }\}$ . Define the $N\times M$ matrix F as follows: if $m\in \mathrm{End}(\epsilon )$ , then $F_{m,\epsilon }=1$ ; otherwise, $F_{m,\epsilon }=0$ . The weight of edge $({\epsilon }_i,{\epsilon }_j)$ can be defined according to Ref. [ 23 ]:

(1) $$W_{{\epsilon }_i,{\epsilon }_j}=\underset{m,d_m>1}{\sum }\frac{F_{m,{\epsilon }_i}{F}_{m,{\epsilon }_j}}{d_m-1}(1-{\delta }_{{\epsilon }_i,{\epsilon }_j})$$

where $d_m$ denotes the degree of node $m$ . If ${\epsilon }_i={\epsilon }_j$ , then ${\delta }_{{\epsilon }_i,{\epsilon }_j}=1$ ; otherwise, ${\delta }_{{\epsilon }_i,{\epsilon }_j}=0$ .

The LDA model is a general probabilistic process for modeling the sparse vectors of the count data. Figure 1 shows the graphical model representation of the LDA model. For the considered text corpus, each document of $D$ documents is a mixture of $K$ latent topics, each of which describes a multinomial distribution of a $W$ -word vocabulary. The generative process of the LDA model for words and documents is as follows:

10.1109/TST.2013.6574677.F001 Fig. 1Graphical model for LDA.

The probability that a word $x_{ij}$ exists in the document $j$ is as follows:

(2) $$p(x_{ij}|{\Theta }_j,\Phi )=\underset{k=1}{\overset{K}{\sum }}p(x_{ij}|{\Phi }_k)p(z_{ij}=k|{\Theta }_j)$$

The parameters of the multinomials for topics in a documents ${\Theta }_j$ and words in a topic ${\Phi }_k$ have Dirichlet priors $\alpha$ and $\beta$ respectively as follows:

$$\begin{array}{c}\hfill {\Theta }_j|\alpha \sim \mathrm{Dirichlet}(\alpha ),\\ \hfill {\Phi }_k|\beta \sim \mathrm{Dirichlet}(\beta ).\end{array}$$

${\Phi }_k$ indicates the words that are important in topic $k$ , and ${\Theta }_j$ indicates the topics that appear in document $j$ ^{[ 25 ]}. Therefore, the joint probability of a document $d_j$ with all the words and topics is as follows:

$$\begin{array}{cc}\hfill p(d_j|& \alpha ,\beta )=\hfill \\ & \int p(\theta |\alpha )(\underset{i=1}{\overset{N_j}{\prod }}\underset{k=1}{\overset{K}{\sum }}p(z_{ij}=k|\theta )p(x_{ij}|z_{ij},\beta ))\mathrm{d}\theta .\hfill \end{array}$$

Finally, by taking the product of the marginal probabilities of single documents, we estimate the probability of a corpus as follows:

$$\begin{array}{cc}& p(D|\alpha ,\beta )=\hfill \\ & \underset{d=1}{\overset{M}{\prod }}\int p({\theta }_d|\alpha )(\underset{i=1}{\overset{N_d}{\prod }}\underset{k=1}{\overset{K}{\sum }}p(z_{ij}=k|\theta )p(x_{ij}|z_{ij},\beta ))\mathrm{d}{\theta }_d.\hfill \end{array}$$

The mixing coefficients for each document and the word-topic distribution are hidden and are learnt from data using unsupervised learning methods^{[ 24 ]}. Model inference approaches that have been used frequently include variational Bayesian, Gibbs sampling, and expectation propagation^{[ 25 , 3 , 26 ]}. The symbols and notations used in this paper are summarized in Table 1 .

When the LDA model is used for the detection of a link community, the line graph should usually be encoded in a set of structured character strings. In the line graph, each edge $e_i$ is characterized by its Interaction Profile (IP), which is defined as a set of its neighboring edges $\{{\mathrm{ne}}_{i,1},{\mathrm{ne}}_{i,2},\mathrm{\cdots },{\mathrm{ne}}_{i,n_i}\}$ and the corresponding weight (Eq. ( 1 )). Formally,

$$\mathrm{IP}(e_i)=\{({\mathrm{ne}}_{i,1},W_{e_i,{\mathrm{ne}}_{i,1}}),({\mathrm{ne}}_{i,2},W_{e_i,{\mathrm{ne}}_{i,2}}),\mathrm{\cdots },$$ $$({\mathrm{ne}}_{i,n_i},W_{e_i,{\mathrm{ne}}_{i,n_i}})\},$$

where $n_i$ denotes the number of $e_i$ adjacent edges. For example, in Fig. 2 , edge $e_0$ has four adjacent edges {1, 2, 5, 6}, and the corresponding weights can be calculated by using Eq. ( 1 ). Each edge is represented by its adjacent edges. The encoding schema guarantees that edges in the same community have similar interaction profiles. Moreover, we consider that the edges in IP are exchangeable and hence, their order is not a concern.

10.1109/TST.2013.6574677.F002 Fig. 2Encoding process.

In our research, we use LDA to model the interactions between the nodes in a network. The main idea of LBLP algorithms is to assume that the adjacent edges of each edge are generated by a mixture of communities, where a community is represented as a multinomial probability distribution over the edges. The mixing coefficients for each edge and the edge-community distribution are unobserved and are learned from data by using unsupervised learning methods. Figure 3 shows the graphical model of the link-LDA model. The generative process for the line graph as follows:

10.1109/TST.2013.6574677.F003 Fig. 3Generative process of line graph.

Therefore, the probability that there is an interaction existing between edges $e_i$ and ${\mathrm{ne}}_{i,j}$ is as follows:

$$p({\mathrm{ne}}_{i,j}|{\theta }_i,\varphi )=\underset{k=1}{\overset{K}{\sum }}p({\mathrm{ne}}_{i,j}|{\varphi }_k)p(p_{i,j}=k|{\theta }_i).$$

Given the hyper-parameters $\alpha$ and $\beta$ , the join distribution of all observed and hidden variables is as follows:

$$\begin{array}{cc}\hfill p(G,P,\Theta ,& \Phi |\alpha ,\beta )=\hfill \\ & \underset{j=1}{\overset{N_i}{\prod }}p(e_i|{\varphi }_{p_{i,j}})p(p_{i,j}|{\theta }_i)p({\theta }_i|\alpha )p(\Phi |\beta ).\hfill \end{array}$$

Given the observed edges $e=\{{\mathrm{ne}}_{i,j}\}$ , the goal of inference is to compute the posterior distribution over the latent link communities $P=\{p_{i,j}\}$ , the mixing proportions ${\theta }_i$ , and the communities ${\varphi }_k$ .

When the LDA model is used for the detection of a link community, the line graph should usually be encoded in a set of structured character strings. In the line graph, each edge $e_i$ is characterized by its Interaction Profile (IP), which is defined as a set of its neighboring edges $\{{\mathrm{ne}}_{i,1},{\mathrm{ne}}_{i,2},\mathrm{\cdots },{\mathrm{ne}}_{i,n_i}\}$ and the corresponding weight (Eq. ( 1 )). Formally,

$$\mathrm{IP}(e_i)=\{({\mathrm{ne}}_{i,1},W_{e_i,{\mathrm{ne}}_{i,1}}),({\mathrm{ne}}_{i,2},W_{e_i,{\mathrm{ne}}_{i,2}}),\mathrm{\cdots },$$ $$({\mathrm{ne}}_{i,n_i},W_{e_i,{\mathrm{ne}}_{i,n_i}})\},$$

where $n_i$ denotes the number of $e_i$ adjacent edges. For example, in Fig. 2 , edge $e_0$ has four adjacent edges {1, 2, 5, 6}, and the corresponding weights can be calculated by using Eq. ( 1 ). Each edge is represented by its adjacent edges. The encoding schema guarantees that edges in the same community have similar interaction profiles. Moreover, we consider that the edges in IP are exchangeable and hence, their order is not a concern.

10.1109/TST.2013.6574677.F002 Fig. 2Encoding process.

In our research, we use LDA to model the interactions between the nodes in a network. The main idea of LBLP algorithms is to assume that the adjacent edges of each edge are generated by a mixture of communities, where a community is represented as a multinomial probability distribution over the edges. The mixing coefficients for each edge and the edge-community distribution are unobserved and are learned from data by using unsupervised learning methods. Figure 3 shows the graphical model of the link-LDA model. The generative process for the line graph as follows:

10.1109/TST.2013.6574677.F003 Fig. 3Generative process of line graph.

Therefore, the probability that there is an interaction existing between edges $e_i$ and ${\mathrm{ne}}_{i,j}$ is as follows:

$$p({\mathrm{ne}}_{i,j}|{\theta }_i,\varphi )=\underset{k=1}{\overset{K}{\sum }}p({\mathrm{ne}}_{i,j}|{\varphi }_k)p(p_{i,j}=k|{\theta }_i).$$

Given the hyper-parameters $\alpha$ and $\beta$ , the join distribution of all observed and hidden variables is as follows:

$$\begin{array}{cc}\hfill p(G,P,\Theta ,& \Phi |\alpha ,\beta )=\hfill \\ & \underset{j=1}{\overset{N_i}{\prod }}p(e_i|{\varphi }_{p_{i,j}})p(p_{i,j}|{\theta }_i)p({\theta }_i|\alpha )p(\Phi |\beta ).\hfill \end{array}$$

Given the observed edges $e=\{{\mathrm{ne}}_{i,j}\}$ , the goal of inference is to compute the posterior distribution over the latent link communities $P=\{p_{i,j}\}$ , the mixing proportions ${\theta }_i$ , and the communities ${\varphi }_k$ .