 in which most of the edges are across different communities and mixture structure, i.e., a kind of structure contains both assortative and disassortative structures, and so on. Due to the rich diversity of community regularities in real-world networks, there may be several unknown types of structures in the networks. Therefore, it is urgent to propose some methods to adapt to the realistic situations and to carry out generalized community detection. So, in this paper, we called these assortative and disassortative structures in the complex networks as generalized communities similar to [30]. Some methods [4] have been proposed to detect generalized communities in complex networks.
In particular, although node attributes may carry essential semantic information of communities, there are few ways to detect generalized communities, that is, detecting broad types of network structural regularities and combining network structures and attributes. Chen et al. [31] developed a Bayesian nonparametric attribute (BNPA) model and explored various types of network structures, but the model did not provide multiple semantic descriptions of the communities.
As a result, considering the rich diversity of community regularities in real networks, nodes attributes can not only improve the quality of generalized community detection but also identify the latent semantic characteristics of communities, identify the generalized communities, and provide semantic descriptions, which are worth studying in the complex network analysis. All the above methods neglect solving this twofold problem. Instead, we propose a unified generative model to detect communities in a wide variety of network structures without any prior knowledge of the certain type of intrinsic regularities in the networks. We also derive the semantic descriptions of the communities by combining the network structure and attributes at the same time. Our model is composed of two closely related parts by a probability transition matrix. The first is the topology part in which communities are described based on a mixture model, assuming that nodes in the same groups have similar link patterns (no matter whether there are more links within the communities or between communities). The second is the attribute part, in which semantic information is identified by the classic topic model (LDA) [23]. We assume that each community has several topics; i.e., the distribution of topics exists in each community. A probability transition matrix is used to reveal the potential corrections between topics and communities. It can handle the problem that the topics from attributes and the communities from networks are not well matched. We finally use a Gibbs sampling algorithm to optimize the objective function. Extensive experiments on a number of synthetic and real networks have shown that our model performs better than some baselines on community detection.
To explore the network structural regularities, some methods for detecting generalized communities have been proposed. Recently, node attributes have attracted extensive attention in the complex network analysis.
Newman and Leicht [30] developed a mixture model to explore the network structure with only links. In this method, the nodes with the same link patterns were divided into the same groups. It modeled the relationships between communities and nodes. The probability that a node was connected to other nodes in the network was related to the community to which the node belonged. Closely connected nodes may not belong to the same community. Thus, a broad of structural signatures could be explored without any prior assumptions about the structure of the network. Hua-Wei et al. [4] focused on identifying the intrinsic structural rules in networks. In this model, the nodes within the same groups had a similar link preference to other groups. A block matrix was defined to denote the probability that the randomly selected edge linked two distinct groups. It could detect broad types of structural regularities by modeling network structures.
There were several methods for content analysis, such as Latent Dirichlet Model (LDA) [23]. The method focused on node attributes and identified the set of nodes whose attributes were similar. Several community detection approaches combining network topologies and node attributes have also been proposed. Some methods only used node attributes to improve the performance of community detection, while others provided the semantic descriptions of communities. Ruan et al. [25] proposed a method for determining the strength of the edges between nodes using content information, which is also applicable to graph clustering. Yang et al. [27] used a discriminative model that combines node attributes and network topologies to detect communities. However, this method focused on community detection without describing the relevant attributes of each community. It did not provide a semantic description of the community. Pool et al. [28] proposed a heuristic method to detect communities by optimizing the community scores. This heuristic method reported too many relatively small communities, some of which had only two or three nodes. Chakraborty and Sycara [32] developed a model based on nonnegative matrix trifactorization method to detect communities via modeling network structure and contents. However, this method mainly used additional attributed information to identify communities and failed to infer the relationship between communities and attributes. Chen et al. [31] developed a Bayesian nonparametric attribute (BNPA) model to explore structural regularities in networks. This model combined network structures and node attributes for community detection and assumed that network structures and node attributes shared the same community memberships; i.e., attribute clusters and network communities were the same. However, attributes and community structures may not always align at all; they could not give multiple semantic descriptions of communities. Wang et al. [33] proposed a model that combined network topology and node semantic information to identify communities. It integrated topology-based community memberships and node-attributes-based community attributes (or semantics) in the framework of nonnegative matrix factorization. The model was based on two important observations: if the community memberships of two nodes are similar, they will have a high probability to produce adjacent edges, and if their attributes are related to the underlying community attributes, they will likely be in the same community. The use of node contents improved the result of community detection and provided a semantic description to the resultant network communities. He et al. [15] introduced a generative model consisting of two parts, one for communities and the other for semantics, exploring the network structure and interpreting the functional modules semantically. The method was only applicable to the network with assortative structures and failed to detect generalized community. More discussions on attribute networks can be found in related surveys by Bothorel et al. [34] and Chunaev [35].
In this section, we give a formal description of the proposed model, i.e., Generalized Semantic Community (GSC) identification, with the purpose of generalized community detection and semantic identification in the networks.
Table 1 shows the notations of the parameters.
Considering the rich diversity of community regularities in real networks, encoding network structure and node attributes simultaneously, and providing the semantic descriptions of the resultant network communities are still the problems that are worth studying in the community detection. However, most existing methods tend to ignore certain aspects of the problems that remain the challenges of current community detection. Given an attributed network, the goal of handling these problems is twofold:(i)How to divide the nodes into communities and content clusters no matter what kind of network structural regularity the network is?(ii)How to identify the correlations between communities and attribute topics to provide the best semantic descriptions of communities?
So the problem can be formalized as, given the adjacency matrix and attributes matrix as well as the number of communities, our goal is to obtain the community assignment for each node and the topic distribution of the communities.
The graphical representation of model.
(2)For each community (a)Sample (b)Sample (3)For each topic in topics(a)Sample (4)For each new node, (a)Sample a latent group assignment (b)For each node with :(i)Sample edge (c)For each of the -th attribute with :(i)Sample (ii)Sample attribute.
We introduce a Bayesian treatment into the model generation process. After the number of communities is given, model parameters are treated as random variables; we generate model parameters,,, and, respectively, by the Dirichlet distribution. The parameters are generated based on some hyperparameters, denoted as a -dimensional vector, an -dimensional vector, a -dimensional vector, and an -dimensional vector. The generative process is as follows.
We use Dirichlet distributions to generate the following model parameters, respectively:where represents a Gamma function. All the communities share the same, and all the topics share the same and.
As denotes the probability that node is in the -th semantic topic while it is divided into -th community, that is, provides the transition from communities to topics, the topic assignment and community membership of node do not always match well. This is why the community may have several topics.
It is subject to,,, and.
To exactly infer that the latent variables and are intractable, we use Gibbs sampling [36] and slice sampling [37] to sample the latent variables and and hyperparameters (,, and ), respectively.
Because the Dirichlet and Multinomial distributions are conjugate, equation (2) can be simplified aswithwhere denotes the number of outlinks whose tail nodes belong to and whose head node is ; denotes the number of nodes in community ; denotes the number of which is generated by topic ; and denotes the total number of topics generated by community.
The inference process is in Algorithm 1.
Inference for GSC.
For each node, given the community assignment for all other nodes, the community probability of the node choosing community iswhere denotes the outlinks of nodes ; denotes the number of outlinks from community except node ; denotes the number of outlinks from community except edges ; denotes the number of nodes in community ; is total number of nodes; denotes the topic labels of the attributes of ; denotes the attributes of ; denotes the topic of ’s -th attribute; denotes the number of node attributes whose topic is except ’s attribute ; denotes the number of nodes’ attributes whose topic is except the attributes of ; denotes the total number of topics generated by community except ; and denotes the attributes of whose topic is.