Exploiting k-Degree Locality to Improve Overlapping Community Detection

1 Introduction

An individual in a social network can not only be regarded as an individual. One's behaviors are influenced by people around her, especially close friends. And her activities will influence others as well. A person always appears in a social network with multiple social identities, e.g., a (former) graduate student, a family member, a club member, a star fan, a company employer, etc. In most cases, her behaviors are related to one or several of these identities. Since identities can be defined by communities, discovering such overlapping communities in social networks becomes an important task for understanding social relationships and activities. This task is known as overlapping community detection [Fortunato, 2010; Gavin et al., 2002; Newman, 2001].

Unlike classic community detection assuming that communities are mutually exclusive, overlapping community detection cannot be directly turned into the traditional graph clustering (i.e., node clustering) problem. Thus, many heuristic methods have been proposed in the past decade to deal with this task. Early approaches pay more attention on links. Clique Percolation [Palla et al., 2005; Kumpula et al., 2008] tries to find all k-cliques (a complete graph with k nodes) and combine those sharing k - 1 nodes to be communities. Link clustering [Ahn et al., 2010], on the other hand, cluster links instead of nodes and assign each node to all communities that its corresponding links belong to. Other recent works such as [Coscia et al., 2012; Whang et al., 2013] select some seed node and use links to expand communities. These methods aim to seek communities via links, but do not address the issue that communities are the actual reason behind links (see Figure 1). Considering a user's ego network [McAuley and Leskovec, 2012], i.e., a network of connections between her friends where communities are social circles categorized manually, the reason for two nodes to build a link is that they are in the same category. For example, the probability of one's college mates to be friends are usually much higher than that of one's random friends.

Based on the idea that "communities generate links", Matrix Factorization based model has been employed for overlapping community detection. To apply this model, we need to set the number of communities and randomly assign users to each community in advance. Then a particular objective function will be adopted to update the community membership for each node. Previously, a typical objective function is to minimize ||A - FF T ||, where A is the adjacency matrix of the network and F is the node-community membership matrix. However, this value-approximation based objective function is problematic in that A only has 0 or 1 in its entry, which is more like a label (i.e., whether there is a link or not) than a real value. In order to tackle this issue, a Preference-based Non-negative Matrix Factorization (PNMF) model [Zhang et al., 2015] has been proposed very recently. Instead of approximating the value, it maintains a pairwise preference order for each node. To be specific, we assume that Ai,j = 1 and Ai,k = 0. Previous models try to make FiF T j close to 1 and FiF T k close to 0 while the preference based model only expects FiF T j to be larger than FiF T k without considering their actual values.

However, PNMF simply separates nodes into two parts, i.e., neighbors and non-neighbors, ignoring the fact that all non-neighbors are not supposed to be treated equally. Inspired by the famous saying "my friend's friend is also my friend", in this paper, we propose a Locality-based Nonnegative Matrix Factorization (LNMF) model to refine the PNMF model by further splitting the non-neighbors into two parts, namely "local non-neighbors" and "distant nonneighbors". We define a "k-degree local network" to distinguish these two kinds of non-neighbors. Given the two assumptions that (1) neighbors are preferred to local nonneighbors and (2) local non-neighbors are preferred to distant non-neighbors, we obtain the objective function by maximizing a product of likelihood. We use the popular stochastic gradient descent as our learning method and provide an efficient sampling strategy. Experiments conducted on realworld datasets show that our LNMF model does outperform the state-of-the-art approaches, indicating that our model assumption makes sense.

The rest of this paper is organized as follows. In Section 2, we formally define the community detection problem and introduce some most related work in more details. Our LNMF model and parameter learning process are illustrated in Section 3. Section 4 includes experimental details and interpretation of results, followed by the conclusions in Section 5.

2 ProblemDefinition and RelatedWork

In this section, we first define the problem of overlapping community detection and then provide an overview of Matrix Factorization based approaches to which our proposed solution belongs. In addition, we will particularly take a look at a Preference-based Non-negative Matrix Factorization (PNMF) model on which our proposed model builds.

2.1 ProblemDefinition

To formally define the problem of community detection, we need to have a graph in the first place. We denote the graph as G(V, E), where V is the node set and E is the link or edge set.

Definition 2.1 (Community). A community C is a subset of V which consists of all nodes with a certain feature.

Since all nodes in a community share a common feature, they are more likely to make friends with each other. Therefore, a community usually has stronger internal connections and weaker external connection, which matches another definition proposed in [Girvan and Newman, 2002].

Definition 2.2 (Community Detection). Given a graph G(V,E), community detection aims to find a set of communities S = {Ci|Ci ̸= ∅,Ci ̸= Cj, 1 ≤ i, j ≤ p}, which maximizes a particular objective function f, i.e.,

where p is the number of communities.

While traditional community detection finds exhaustive and disjoint communities, i.e., C1 ⋃ · · · ⋃ Cp = V and Ci ⋂ Cj = ∅ for any i ̸= j, overlapping community detection has no such constraints, which is more general and realistic in real world.

2.2 Matrix Factorization Based Approaches

As we mentioned, matrix factorization is a popular class of methods to deal with overlapping community detection problem. It sets the number of communities in advance and then learns to assign each node to its corresponding communities. The objective can be formally defined as follows.

Definition 2.3 (Overlapping Community Detection via Matrix Factorization). Given a graph G(V, E) with its adjacency matrix A ∈ {0, 1}n×n , the objective of overlapping community detection via matrix factorization is to find a node-community membership matrix F ∈ Rn×p whose entry Fu,c represents the weight of node u ∈ V in community c ∈ C so that F can minimize a particular loss function l, i.e.,

where n is the number of nodes, p is the number of communities and C is the set of communities. In the end, we obtain the final set of communities C according to F .

Here we would like to review several important work in this class. [Psorakis et al., 2011] is the earliest method which uses the basic ||A - WHT || as its optimization objective. Due to the vague social meaning of W and H, [Wang et al., 2011] refines the objective function to ||A-FF T ||. [Zhang and Yeung, 2012] extends the matrix factorization model to matrix tri-factorization model by incorporating a community interaction matrix B, which results in a objective function of ||A - FBF T ||. [Yang and Leskovec, 2013] explicitly defines the probability of having an edge between u and v by a function of Fu and Fv, then generates the likelihood function by fitting the original graph. Though these objective functions are different, they are all based on value-approximation, which is problematic because the 0/1 value in adjacency matrix is more like a label than a value.

2.3 A Preference-based NMFModel

The Preference-based Non-negative Matrix Factorization model [Zhang et al., 2015] is based on the intuitive idea that two nodes are more likely to become friends if they share more common communities. Recall the aforementioned "communities generate links" assumption, this model wants to obtain communities by extracting node preference information from links.

The basic assumption of this model can be represented as

where ru,i is the preference of node u on node i, i.e., how much u wants to build a link with i, and Au,i is the corresponding entry in adjacency matrix A.

For each node u, the objective function is to maintain a preference order of all the other nodes given the nodecommunity membership matrix, which is denoted as

By applying the results from [Rendle et al., 2009] and denoting the set of u's neighbors as N +(u) and the set of u's non-neighbors as N -(u), the above objective function can be simplified to the form of

P(ru,i > ru,j|F) are defined as σ(Fi · F T j - Fi · F T k ), where σ(·) is the sigmoid function. The rest steps are quite standard so we will not go through details.

3 A Locality-based Non-negative Matrix Factorization (LNMF) Model

In this section, we first define the concept of k-degree locality and then formalize our LPNMF model in the scenario of community detection. We will also briefly talk about the process of parameters learning and provide several candidates of sampling strategy.

3.1 Preliminaries

Definition 3.1 (k-Degree Local Network). Given an undirected and unweighted graph G, for a node u ∈ G, u's kdegree local network Lk(u) is the subgraph consisting of all nodes whose shortest path length to u is less than or equal to k.

According to the definition above, L0(u) consists of only node u, L1(u) is the subgraph including node u and all its neighbors, L∞(u) is the whole graph, etc. We denote the node set of Lt(u) except u itself as Vt(u), where t = 1, 2, · · ·.

Now we further define the terms of "local non-neighbors" and "distant non-neighbors".

Definition 3.2 (k-Degree Local Non-neighbors). Given a k-degree local network Lk(u), the set of k-degree local nonneighbors Sk(u) is defined as Sk(u) := Lk(u)\L1(u), where k ≥ 1.

Definition 3.3 (k-Degree Distant Non-neighbors). Given a k-degree local network Lk(u), the set of k-degree distant non-neighbors Tk(u) is defined as Tk(u) := L∞(u)\Lk(u), where k ≥ 1.

We can see that when k = 1, Sk(u) = ∅ and Tk(u) = N -(u). In this case, our model degrades to the PNMF model. When k ≥ 2, our model will have a new class of nodes in preference system. Thus, our model is actually a generalization of the PNMF model.

A summary of notations is shown in Table 1. Four simple propositions can be drawn from the above notations.

Proposition 3.1. Vk(u) = N +(u) ⋃ Sk(u).

Proposition 3.2. N +(u) ⋂ Sk(u) = ∅.

Proposition 3.3. N -(u) = Sk(u) ⋃ Tk(u).

Proposition 3.4. Sk(u) ⋂ Tk(u) = ∅.

3.2 Model Assumption

Recall the basic assumption of PNMF in Equation 3. Incorporating the concept of k-degree local network, we can exploit k-degree local non-neighbors to enhance the old model assumption. The new model assumption for our LNMF model can be represented as

where ru,p is still the preference of node u on node p. It means (1) neighbors are preferred to local non-neighbors; (2) local non-neighbors are preferred to distant non-neighbors. These two assumptions are quite intuitive. Notice that when k = 1, the new model assumption degrades to the old one.

We also adopt two independence assumptions, i.e., node independence and pair independence assumptions, listed in [Zhang et al., 2015] in order to formalize our model.

• Node independence. The preference order of each node is independent with that of any other node. There will be a link between u and v if and only if u prefers to build relationship with v and symmetrically v prefers to build relationship with u.
• Pair independence. For a fixed node i, its preference on j and k is independent with its preference on u and v when j, u ∈ N +(i) and k, v ∈ N -(i).

3.3 Model Formulation

Given the above model assumptions, we are ready to present our LNMF model in a formal way. Since nodes are independent of each other, we can consider one node at first.

For each node u, the optimization criterion is to maximize the likelihood of preference order which can be represented as a product of pairwise preferences, i.e.,

where δ(·) and ξ(·) are two indicator functions that

Algorithm 1 Community Detection via LNMF

Input: G, the adjacency matrix of original graph Output: F, the node-community membership matrix

• 1: initialize F
• 2: compute initial loss
• 3: repeat
• 4: for num samples = 1 to sample size do
• 5: sample (u, i, j, d) according to Algorithm 2
• 6: for each entry Θ in Fu, Fi, Fj and Fd do
• 7: update Θ according to Equation (10)
• 8: Θ ← max(Θ, 0)
• 9: end for
• 10: end for
• 11: compute loss
• 12: until convergence or max iter is reached

and

.

Recall the four propositions in preliminaries that Vk(u) and N -(u) can be split into two disjoint sets with different levels of preference. Following the scheme argued in [Rendle et al., 2009; Zhao et al., 2014], we can simplify Equation 6 to

Applying the sigmoid function σ(x) := 1 1+e-x to interpret P(ru,i ≥ ru,j|F), i.e., P(ru,i ≥ ru,j|F) = σ(ˆx(u, i) - ˆx(u, j)), we sum up the log-likelihood functions of all nodes:

where ˆx(u, i) := Fu · F T i can be regarded as the correlation between u and i, and λ(u) := |N +(u)| |Tk(u)| can be regarded a coefficient of local influence.

In the end, to prevent our model from overfitting, we add a regularization term reg(F ) = ||F ||2F , which is the Frobenius norm of the node-community membership matrix. The final objective function l is

where λr is a regularization coefficient.

3.4 Parameter Learning

As an efficient and widely-used paradigm for parameter learning, stochastic gradient descent (SGD) is employed as

Algorithm 2 Sampling Strategy

Input: G, the adjacency matrix of original graph Output: (u, i, j, d), a quadruple to perform a step in stochastic gradient descent

• 1: sample node u from V uniformly at random
• 2: sample node i fromN +(u) uniformly at random
• 3: sample node j from Sk(u) uniformly at random
• 4: sample node d from Tk(u) uniformly at random

our learning algorithm. Distinguished from the traditional batch gradient descent which computes Equation 9 in each iteration, SGD only picks a small number of random samples to perform update. In our case, a sample is a (source, neighbor, local non-neighbor, distant non-neighbor) quadruple. Mathematically, we calculate the derivative of our final objective function l by

where is Θ can be any entry of the node-community membership matrix F . For the non-negative constraints, we apply a projected gradient method proposed in [Lin, 2007], which maps the parameter vector back to the nearest point in projected space, in our case, the non-negative space.

The whole process is described in Algorithm 1. Let sample size be t. The time complexity of each iteration is O(tp) and the space complexity is O(np), where n is the number of nodes and p is the number of communities.

3.5 Sampling Strategy and Other Issues

Due to the nature of stochastic gradient descent, sampling strategy matters to both running time and performance. More than what PNMF did, we need to sample a set of quadruples for each learning step. The process is described in Algorithm 2.

For the sampling of j, we need to pre-process the whole graph to record a set of local nodes of each u in the graph. By using the fact that N -(u) = Sk(u) ⋃ Tk(u), we keep sampling a random node until we get a node neither in N +(u) nor in Sk(u) and let d be this node.

Moreover, there are several remaining issues to be discussed.

• The number of communities. The nature of matrix factorization needs us to set the number of communities which are unknown in advance. A cross-validation paradigm is used. In details, we reserve 10% of nodes as validation set at first. After learning the nodecommunity membership matrix F , we compute the sum of log-likelihood function for all nodes in validation set via Equation 7. Since the computational cost is huge for cross-validation, only a small set of quadruple will be sampled.
• The community membership threshold. Obtaining the node-community membership matrix F is still one step away from getting the final node-community correspondence. We need to set a threshold to decide whether a community accepts a node. We employ the approach

in [Zhang et al., 2015] to deal with this issue. In short words, we set a probability threshold to P(ru,i ≥ ru,j|F) and use the sigmoid function to reversely compute the lower bound of community membership weight assuming that u, i share one community but u, j do not share any community.

• The convergence criterion. First, we randomly generate a subset of quadruples to be our loss sample and compute initial loss on this set according to Equation 9. After each iteration, we need to compute loss again and we stop stochastic gradient descent when the absolute difference between current loss and previous loss is smaller than a very small percentage, say ϵ, of initial loss.

4 Experiments

In this section, we compare our LNMF model with both classic and state-of-the-art overlapping community detection methods on various real-world datasets. We will show our experimental results with two metrics, namely modularity and F1 score, and have a brief discussion.

4.1 Data Description

Six benchmark networks collected by Newman 1 are used as our datasets. These networks are relatively small and have no ground-truth communities. Basic information of these datasets can be found in Table 2.

Moreover, we choose three large networks with groundtruth communities collected by SNAP 2 [Yang and Leskovec, 2012] to test the scalability of our model. These networks are of different types:

• YouTube dataset: a social network of a video-sharing web site.
• DBLP dataset: a collaboration network of research paper authors in computer science.
• Amazon dataset: a products co-purchasing network based on Customers Who Bought This Item Also Bought feature of the Amazon website.

Simple statistics for these three datasets are shown in Table 3.

4.2 Experimental Setup

We conduct our experiments on a computer with a Xeon 2.60GHz CPU and 64GB memory.

1 http://www-personal.umich.edu/ mejn/netdata/

2 http://snap.stanford.edu/data/

Comparison methods. We select both classic and state-ofthe-art methods to compare with our model. The latter four are Non-negative Matrix Factorization (NMF) based models.

• SCP [Kumpula et al., 2008] accelerates the original CP method [Palla et al., 2005] in a sequential manner. We set k to be 4 or 5 when finding k-cliques.
• LC [Ahn et al., 2010] clusters link instead of node to get overlapping communities. We ignore all communities with only one or two nodes since they are meaningless.
• BNMF [Psorakis et al., 2011] is one of the earliest work which applies MF into community detection. Squared loss is used as loss function.
• BNMTF [Zhang and Yeung, 2012] incorporates a community interaction matrix into the classic MF to become a Matrix Tri-Factorization model. Squared loss is used as loss function.
• BigCLAM [Yang and Leskovec, 2013] is claimed by its authors as a scalable model. It can search for the best number of communities given a range.
• PNMF [Zhang et al., 2015] is the model on which our proposed model builds.

Evaluation metrics.

• Modularity. We use the classic modularity as our metric for Newman's datasets. Modularity Q is defined as

where m is the number of links, V is the node set, A is the adjacency matrix, d(u) is the degree of node u, and Cu is the set of communities to which node u belongs. This definition indicates that for each node pair (u, v) which shares communities, its contribution to modularity is positive if u, v are linked and is negative otherwise. It matches our intuition that nodes inside one community tends to build links with each other.

• F1 score. For SNAP datasets with ground-truth communities, F1 score is obviously one of the best measurements. The F1 score of a detected community Si is defined as the harmonic mean of precision(Si) and recall(Si), where precision(Si) and recall(Si) are defined as

and

where Cj is the node set of a ground-truth community. The average F1 score for the set of detected communities S is

Setting the k. Remember that if we set k = 1 in k-degree local network, our model will degrade to the PNMF model. According to our observation on several datasets, if k is set to be larger than 2, the average number of common communities two nodes in a k-degree local network share is not significantly larger than that two random nodes in the whole network share. Thus, we set k to be 2, which means only a friend's friends are considered as local non-neighbors.

4.3 Results

We set the regularization coefficient to be 0.5 and the convergence parameter ϵ to be 0.001 for all experiments. The sample size t is determined according to data size. For Newman's datasets, we set t = m, i.e., the number of links. For SNAP datasets, we set t = 10√n in order to finish one iteration without taking too much time, where n is the number of nodes. The maximum times of iteration is set to 100, though in fact all datasets converge before reaching the limit.

Table 4 shows the performance of our LNMF model on Newman's datasets. From the results we find that under the metric of modularity, our LNMF model outperforms all baseline methods on all datasets.

Table 5 shows the our experimental results on SNAP datasets. The other baselines methods are not listed here since none of them can finish all three datasets in time. This fact can reflect the scalability of our LNMF model to some extend. It can be seen that our model outperforms BigCLAM on all datasets and has improvement over PNMF on two of three datasets. For YouTube, we find its community formation pattern quite random due to small size of communities and large variety of users. In other words, our model assumption does not fit the community pattern of this dataset so well. This may explain why LNMF fails to have improvement on it. The running time of one iteration is about one or two hours for DBLP and Amazon. For YouTube, it takes about four to five hours to finish an iteration.

The convergence speed of our learning algorithm on Amazon and DBLP is illustrated in Figure 2. A point in the figure represents the ratio of current loss to initial loss after i-th iteration. The results show that our LNMF can converge within a fair number of iterations. In fact, if we do not consider the regularization term, the final losses of both datasets are less than 10% of the initial loss.

5 Conclusion And FutureWork

In this paper, we propose a Locality-based Non-negative Matrix Factorization model to improve the performance of existing work on overlapping community detection. Our LNMF model is based on a pairwise preference learning scheme. We exploit local area around a node formally defined as k-degree local network to enhance the previous preference system. In details, we extend a two-level preference system which only distinguish neighbors and non-neighbors to a three-level preference system which split the set of non-neighbors into local non-neighbors and distant non-neighbors. Experiments on several real-world datasets including large ones with groundtruth communities show that this extension can indeed improve the quality of overlapping community detection.

Our model can be further generalized by extending the preference system from three-level to n-level. Mathematically, according to the notations in Section 3.1, now Pk(u) := Lk(u)\Lk-1(u) for each k ≥ 1 is a node set of a particular preference level of node u and u's preference on Pi(u) is larger than its preference on Pj(u) if i > j. For model formulation, we only need to modify a few spots to make it a more general one. However, our learning algorithm is not efficient enough. Specifically, a natural extension of our sampling strategy suffers two main problems: (1) for different nodes, the upper limit of k is different; (2) for each node u, pre-processing the whole graph to record node sets of all preference levels is equal to a breath-first search starting from u, which is too expensive for large-scale networks. We plan to first conduct empirical study to see whether this extension makes sense. If it does, we will try to find solutions for the problems mentioned above.

Acknowledgement

The work described in this paper was fully supported by the National Grand Fundamental Research 973 Program of China (No. 2014CB340401 and No. 2014CB340405), the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK 413213 and CUHK 415113), and Microsoft Research Asia Regional Seed Fund in Big Data Research (Grant No. FY13-RES-SPONSOR-036).