Self-Guided Community Detection on Networks with Missing Edges

1 Introduction

With the development of computer technology and the massive increase in data, network has become an important and ubiquitous structure in real world, which can describe relationship (represented by edges) between entities (represented by nodes). Such networks include, for example, social networks, biological networks and citation networks, just to name a few [Barrat et al., 2008; Cohen and Havlin, 2010; Newman, 2018]. Community detection, one of the most important tasks in network analysis, has attracted great attention. In general, the goal of community detection is to discover functionally related modules which generally has the following structural characteristics: nodes in the same community are densely connected whereas nodes in different communities are sparsely connected [Girvan and Newman, 2002]. Community detection has been successfully applied to a wide range of areas. For instance, social networks allow us to recommend advertisements to users with similar hobbies; Protein-protein interaction networks permit us to discover specific functional modules of proteins. Many community detection algorithms have been proposed. They include, for example, modularity optimization based methods [Newman and Girvan, 2004; MacMahon and Garlaschelli, 2015], deep learning based methods [Rozemberczki et al., 2018; Wang et al., 2017; Li et al., 2020] and stochastic block models (SBM) [Ball et al., 2011; Peixoto, 2014; Karrer and Newman, 2011; Yang and Leskovec, 2013; Zhang et al., 2015; Ye et al., 2018].

∗Corresponding author.

†Contributed equally to this work.

These algorithms mentioned above assume that the observed networks are complete. However, there are missing edges in many real-world networks. For instance, some users on Twitter may hide part of their friends list, making the edge between the corresponding pair of users unobserved in the network [Lin et al., 2013]. In the terrorist organization network [Lin et al., 2013], where each node represents terrorist activities, and the edge between two nodes indicates that two activities come from a same organization, we may not know which terrorist organization carried out a terrorist activity. Thus, the relationships between some terrorist activities are unknown. Hereafter network with missing edges is called edges-missing network. As the topology information plays an important role in community detection, intuitively using traditional algorithms designed for complete networks directly on edges-missing networks could compromise community detection accuracy. This is verified by Gabielkov [2012], where various different community detection algorithms were tested on many edges-missing networks. In addition, missing edges have been shown to have impact on some important network properties, such as the diameter, the centrality or the degree distribution [Huisman, 2009; Borgatti et al., 2006]. Therefore, it is necessary to design community detection algorithm that is particularly suitable for edges-missing networks.

Recently, some community detection algorithms for edgesmissing networks have been proposed. These methods fall into two categories. The first category includes two-stage algorithms [Tran et al., 2018]. Concretely, the first stage entails performing link prediction to recover the missing edges, and the second stage entails performing community detection on the complemented network. The second category includes methods conducting community detection and link prediction simultaneously in a unified framework [Shao et al., 2019]. Such as CLMC [Shao et al., 2019], is one of the most representative algorithms in this category, whose goal is to learn a similarity matrix to detect communities and a supplement matrix to predict missing edges simultaneously in a unified framework. It is worth noting that all these algorithms assume that the more missing edges the algorithm can predict correctly, the more accurate the community detection is. However, the assumption may not hold in reality as not all edges play the same role in community detection. For some nodes, even several edges are missing, their community memberships are still clear. Conversely, for other nodes, even one missing edge could change their community membership. For example, we applied this representative unified method CLMC on the classical community detection dataset, Zachary's Karate club network, and we removed 10% edges randomly from the network, making it an edges-missing network. The result is shown in Figure 1 (a), where although most of edges are predicted correctly, the results of community detection are still biased, i.e., node 2 is divided into a wrong community. This is because the correctly predicted edges do not play an important role in community detection, echoing what we illustratively explained earlier. For instance, removing edge (1, 17) (which is correctly predicted) will not change the community membership of node 1 and node 17. This is due to the fact that the true community of node 1 and 17 are easy to determine, and most of their neighbors only belong to one community and they have few connections to another community. This is also the case for edges (29, 33) and (1, 7). On the contrary, node 2 is located at the boundary of two communities, which is difficult to determine its community membership. For this node, the algorithmCLMC did not predict its missing edges which indirectly led it being placed into the wrong community. In fact, link prediction algorithms prefer to predict the intra-community edges that play less important role in community detection. Thus, simple combination of link prediction and community detection cannot handle the problem of community detection on edgesmissing networks in essential.

To address this problem, we proposed a community selfguided generative model for jointly completing the edgesmissing network and identifying communities. Unlike the state-of-the-arts such as CLMC, our model predicted the missing edges (2, 3) correctly and divided node 2 into the correct community (as shown in Figure 1 (b)). The improvement is brought about by accommodating two sets of variables in our model, one for recovering the missing edges, and one for characterizing communities. In this new model, recovering missing edges is guided by community detection in such a way that we predict the edges that are important for identifying communities. Meanwhile, community detection is also affected by completing the network. For training the model, we developed an effective method that combines a nested Expectation-Maximization (EM) algorithm and MetropolisHastings sampling. We evaluated our model on a variety of real-world networks and compared with different kinds of methods, including methods for complete networks, twostage methods and unified end-to-end methods for edgesmissing networks. Empirical results show the significant superiority of a model over the existing methods.

2 The Community Self-Guided Approach

In this paper, we developed a community self-guided generative model for completing the edges-missing network and discovering community structure at the same time. To train the model, we developed an effective method for combining a nested Expectation-Maximization (EM) algorithm and Metropolis-Hastings sampling approach.

2.1 The Model

Considering an observed network GO (V, EO) with n nodes and |EO| edges. We use GM (V,EM) to represent a latent network GM (V,EM), where EM denotes the missing edges of the observed network GO. We define the complete graph containing the observed network GO and the latent network GM as G(V,E), where E = EO ∪ EM. We use A = (aij)n×n to denote the adjacent matrix of the observed network GO, where aij = 1 if an edge exists between node i and node j, or 0 otherwise. We use Z = (zij)n×n to denote the adjacent matrix of the latent network GM, where zij = 1 if the edge between node i and node j is missing, or 0 otherwise. Then, with a community assumption, complete network G (where G = GO ∪ GM) can be viewed as an ensemble of c probabilistic communities, {G1,G2, . . .Gc}, where every node has a probabilistic membership in each community Gk, k = 1, 2 · · · c. For each community, it can be regarded as a random graph with no community structure, and we use a random-graph null model to model each probabilistic community as Jin [2015]. Note that the community memberships are designed for the complete network including both the observed part and the missing part.

Now we give the specific definition of the model. We use dik to denote the expected degree of node i within community Gk. As every probabilistic community Gk is a random graph, the expected number of edges between node i and node j in community Gk is:

Taking all k probabilistic communities into account, the expected number of edges between node i and node j can be defined as:

The exact number of edges between nodes i and j is Poisson distributed about this mean value ̂ wij. Then, the likelihood function that the complete network G (including the observed network Go and the latent network GM) was presumably generated from the model can be defined as follow:

where A denotes the adjacent matrix of the observed network GO, Z the adjacent matrix of the latent network GM, and D = (dik)n×c the expected degrees of nodes for all communities. In fact, the latent network GM is not known, and the missing edges in Z can be considered as latent variables.

In this case, our model integrates the missing edges and the community memberships in a unified generative model. With this configuration of Z, it can help to produce the complete network which helps the community detection best. Then, the latent network and community structures can be learned simultaneously and are mutual enhancement. By doing so, the model has better performance than the two-stage methods. More importantly, compared to previous unified frameworks, such as CLMC, our model focuses on the important nodes and those from community boundary based on the parameter D. Furthermore, by calculating the subordination of nodes degree participating in communities, our model can recognize latent edges that are the most important for community detection. To sum up, our model is self-guided by community structure and designed for missing edge networks.

In our model, the model parameters dik is the community information and they are also used to completing the missing part. Given dik, the expected number of edges ̂ wij between any node i and node j can be obtained, and then the probability of the existence of missing edge between any unconnected pair nodes of the observed network GO can be modeled by Bernoulli distribution with parameter ̂ wij. The completing missing edges and the discovering community structures are closely intertwined. Once the missing part Z is obtained, the model parameters dik can be estimated by maximizing the likelihood function. After the model parameters dik are estimated, the configuration of the missing part that results in the largest increase of the likelihood function is selected. The selected configuration will result in a new potential maximum value of the likelihood function. Then the model parameters dik is refined by finding the optimal value corresponding to the new potential maximum value. As we keep alternating between estimating the missing part Z and model parameters dik, the community structure becomes clearer and clearer.

Although the determination of the missing part Z has been modeled by Bernoulli distribution with the expected number of edges as its parameters, the sample Z that is directly generated by Bernoulli distribution is highly random. In order to minimize the impact of randomness on likelihood and generate a confident sample Z, we develop a MetropolisHastings sampling process with a Markov chain. According to Markov property, given sampled Z (t) , the next candidate sample Z (t+1) can be generated. Then we accept or reject this new Z (t+1) according to an acceptance probability. This process continues until reaching a steady state. According to the mechanism of Metropolis-Hastings sampling, when it reaches a stationary state, the sampled samples can effectively improve the likelihood, and the determined missing part can improve the performance of community detection.

2.2 The Model Inference

We then describe how to infer community structure and the latent network simultaneously on edges-missing networks by using a nested Expectation-Maximization (EM) algorithm with Metropolis-Hastings sampling.

E-Step with Metropolis-Hastings Sampling

Given the model parameters D, we use Metropolis-Hastings sampling to determine the missing part Z from the Bernoulli distribution with parameter ̂ W = ( ̂ wij)n×n , where ̂ wij is the expected number of edges between node i and node j. To make the sampling process effective, we adopted the strategy of [Kim and Leskovec, 2011] which can produce a sample of Z in constant time. According to Markov property, given the current sample Z (t) , the next candidate sample ˜ Z can be generated. The new sample ˜ Z is generated based on Z (t) by removing one edge randomly from Z (t) and adding another edge to it as [Kim and Leskovec, 2011]. This sample ˜ Z is accepted as the next sample Z (t+1) with an acceptance probability. If the new sample Z (t+1) is rejected, the current sample Z (t) is taken as the next sample Z (t+1) . The acceptance rate R ( ˜ Z, Z (t)) is defined as:

where the transition probability P (Z (t)) P ( ˜ Z | Z (t)) can be defined as:

where Z (t) \e1, e2 means edges e1 and e2 are not in Z (t) , and E(t) M denotes the set of edges in sample Z (t) . Similarly, P( ˜ Z)P (Z (t) | ˜ Z ) is defined as:

The final acceptance probability can be derived as follows:

Using the above acceptance probability, we generate samples of Z and get a mean matrix ¯ F as follows:

where W is the warm-up iterations and S is the total number of samples. ¯ F is an n × n matrix, where each element fij in ¯ F represents the strength between node i and node j. The confident sample Z can be derived through ¯ F by setting a threshold value α:

M-Step with Nested EM

In M-step, we consider the missing part Z and the observed part A are given, and the goal is to estimate the model parameters D that maximize the likelihood function in (3), that is, finding the parameters that fit the model to the given data (the missing part Z and the observed part A) best. Here maximizing the likelihood is typically done by maximizing the logarithm of the likelihood, which makes the differentiation much simpler while giving the exact same result. Taking the logarithm of (3), we can get the log-likelihood:

Since directly maximizing (10) by differentiation will lead to a set of nonlinear implicit equations for the model parameters dik, here we apply an EM algorithm to solve this problem. Applying Jensen's inequality to (10), we get:

where ¯L is a lower bound of L and the probabilities qij,k can be freely chosen provided satisfy ∑k qij,k = 1. And the equality holds at:

Maximizing the log-likelihood L with respect to the model parameters dik equates maximizing its lower bound ¯L(dik, qij,k) with respect to both the model parameters dik and the probabilities qij,k.The EM algorithm for this dual maximization is to iteratively maximize qij,k(i.e., the E-step) and then maximize the model parameters dik(i.e., the Mstep),which has been proved to converge to a local maximum.

For the E-step, we need to make ¯L = L. Given the optional model parameters dik,the optimal values of qij,Z can be obtained by Eq.(12); For the M-step, given the optional values of qij,k, the optional dik can be found by differentiating (12) under the constraints ∑k dik = di, which gives:

3 Experiments

We first compare our method SGCD with some state-of-theart methods on real networks with ground-truth communities, and then on networks without known communities. Next, we give a case study analysis to show why our method works and, moreover, why it is superior to the link prediction enhanced end-to-end strategies. We finally test its effectiveness by varying the radio of missing edges, as well as its stability on the unique hyperparameter α.

3.1 On Networks with Known Communities

We test the performance of our method SGCD on six widelyused real networks with known communities (Table 1). Since these networks are fully observed, according to [Shao et al., 2019], we randomly removed 20% existing edges for each network to produce edges-missing networks. To be specific, for each network we generated 50 edges-missing network instances randomly, and calculated the mean of the performance of each algorithm tested on these networks.

We compare SGCD with some most related methods (Table 2). BigClam [Yang and Leskovec, 2013], DANMF [Ye et al., 2018] and GEMSEC [Rozemberczki et al., 2018] are traditional community detection methods which do not consider missing edges. NM-SBM [Peixoto, 2018] and CLMC [Shao et al., 2019] are designed for finding communities on edgesmissing networks. MNDP [Jin et al., 2015] is the base of our method not considering missing edges, MNDP2Stage is the two-stage version of MNDP considering missing edges (i.e., we use the results of the first run of MNDP to fill up missing edges for its second run), and MNDPFull is MNDP running on the original complete network without removing edges. SGCDFull is our SGCD running on the complete network. We use the default settings for all the baselines, and set α= 0.5 for our method (see the parameter analysis section later). We run each method 20 times on each network instance and select the result corresponding to the maximum likelihood since they are mainly model-based methods. We use Normalized Mutual Information (NMI) as the measure metric as it is widely-used in community detection.

The results are shown in Table 2. As shown, our SGCD performs the best on all the networks with missing edges, and is very close to the gold standard, i.e., MNDPFull. Particularl, our SGCD outperforms 7.39% on average over the second-best method CLMC (which is also an end-to-end model but uses link prediction to reinforce community detection). In addition, thanks to the effectiveness of this new self-guided mechanism, SGCDFull can even improve MNDPFull which can be taken as an upper bound of the link prediction-enhanced methods like CLMC. This further shows that, SGCD not only has the superiority on networks with missing edges, but can also improve community detection performance on full networks. This may further explain why it is more effective than the link prediction based community detection for edge-missing networks.

3.2 On Networks without Known Communities

We further test SGCD on several real networks without known communities (Table 3). Because the model-based methods compared need the number of communities, we derive it by using the well-known Louvain method, as suggested by [Newman and Girvan, 2004]. While this number may not be completely correct, it does not affect the fairness of the evaluation and comparison of these methods in general. We use modularity Q as the evaluation metric which is often the most widely-used metric in this case.

The results are shown in Table 4. As shown, SGCD performs best on 3 out of the 5 networks, while CLMC performs best on the remaining two networks. But on average, SGCD improves CLMC 0.1791 under the condition that Q is typically in the range of 0.2 to 0.8. Furthermore, on the complete networks, SGCDFull improves MNDPFull 0.0906 on average. This further validates the effectiveness of the new framework with our self-guided mechanism.

3.3 Why SGCDWorks

We give an illustrative experiment to show why our method SGCD works on networks with missing edges. Here we select two representative algorithms MNDP and CLMC to be compared, and use the dolphin social network with 20% missing edges as a sample dataset. The results of MNDP, CLMC and SGCD are shown in Figure 3 (a), (b) and (c) respectively. Compared to MNDP, our SGCD divides nodes 28 and 39 into correct communities by producing important edges, such as edges (28, 36) and (28, 39). Compared to CLMC, our SGCD divides node 39 into the correct community. In this case, while CLMC predicts many edges correctly, as most of these edges do not play an important role in community detection, the result is still compromised. Conversely, thanks to the effective self-guided mechanism, our SGCD produces edges like (28, 39) that significantly improve community structures. This could be the reason why our new framework is effective for networks with missing edges, and better than other types of methods (e,g., CLMC) which allow missing edges.

3.4 Varying the Ratio of Missing Edges

The goal here is to show the robustness of SGCD on networks with varying the ratios of missing edges. Here we only show the results on two sample networks due to space limitation as other networks are similar. For each network, we chose eight different edges-missing ratios, i.e., from 0% to 35% with step size of 5%. (We did not consider the ratio higher than 40% because it will make the network too sparse to be detected, according to the theoretical limits of detectability [Decelle et al., 2011]) The results are shown in Figure 3, where our model achieves the best performance in most cases. Even when the ratio is 0%, which means MNDP reduces to MNDPFull, our SGCD still performs better. This further demonstrates the advantages of our new model due to this community self-guided mechanism.

3.5 Parameter Analysis

Our model has only one hyperparameter α which is to control the threshold of the probability of filling out edges. We select the same networks as those in the above section as examples to test the sensibility our SGCD on α. As shown in Figure 4, when α approaches 0.0, the result of SGCD was inaccurate compared to MNDP. This is because the lower the α, the more noise edges are added. As a result, these noise edges may produce negative effects on inferring community structures based on the observed edges. When α approaches 0.9, which leads to very few edges added to observed data, the NMI accuracy of SGCD and MNDP are similar. However, when α is in the range of 0.4 to 0.5, SGCD is often stable and gives better results and this trend is similar on other networks. Therefore, we set α = 0.5 without loss of generality.

4 Conclusion and Discussion

In this paper, we studied the problem of community detection on edges-missing networks, and proposed a community selfguided generative model SGCD. The model jointly formulates missing edges and community memberships in a unified likelihood function, which can realize predicting important edges for community detection by choosing edges that increase likelihood mostly. We developed an efficient inference method by using a nested EM algorithm with MetropolisHastings Sampling to train the model. We finally tested our SGCD on eleven real-world edges-missing networks with or without ground-truth, and compared with several state-of-theart approaches. The results showed that this new approach outperformed all the methods compared.

The new model is still not perfect. That is, when the ratio of missing edges reaches a certain level, it will hard to find edges so effective to help community detection. While there are several works working on it, it is still a bank for edgesmissing networks which we will take as the future work.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (61876128, 61832014, 61772361, 61902278), the Tianjin Municipal Science and Technology Project (Grant No. 19ZXZNGX00030) and University Facilitating Fund at Geroge Washington University.