{'fraction_non_alphanumeric': 0.03410215980345422, 'fraction_numerical': 0.012430787283194602, 'mean_word_length': 4.307901907356948, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving PageRank for Local Community Detection

Community detection is a classical problem in the field of graph mining. While most algorithms work on the entire graph, it is often interesting in practice to recover only the community containing some given set of seed nodes. In this paper, we propose a novel approach to this problem, using some low-dimensional embedding of the graph based on random walks starting from the seed nodes. From this embedding, we propose some simple yet efficient versions of the PageRank algorithm as well as a novel algorithm, called WalkSCAN, that is able to detect multiple communities, possibly overlapping. We provide insights into the performance of these algorithms through the theoretical analysis of a toy network and show that WalkSCAN outperforms existing algorithms on real networks.


INTRODUCTION
Community detection is a fundamental problem in the field of graph mining [14], with applications to the analysis of social, information or biological networks. The objective is to find dense clusters of nodes, the underlying communities of the graph. While most existing algorithms work on the entire graph [15] [3][17] [11], it is often irrelevant in practice to cluster all nodes. A more practically interesting problem is to detect the community to which a given set of nodes, the so-called seed set, belong. This problem, known as local community detection or seed set expansion, is particularly relevant in large graphs where the exploration of the whole network is computationally expensive, if not impossible. It is also motivated by the recent empirical results in [7], showing that the community structure of real networks is much more intricate than a simple partition, as implicitly assumed by most algorithms working on the entire graph.
The problem of local community detection consists in recovering some unknown community C in a graph given some The present work is currently under review by an international conference.
subset S ⊂ C of these nodes, the seed set, which may be provided by an expert for instance [9]. A simple approach to this problem is to add at each step the most important node according to some goodness metric [5][10] [4] [13]. Another class of algorithms use random walks starting from the seed set [9][1] [8] [12]. For instance, the classical PageRank algorithm can be combined with some stopping criterion based on a goodness metric, like conductance or modularity [19][18] [2].
In the present paper, we propose a novel approach to this problem. Specifically, we use a random walk of T steps starting from the seed set S to embed the graph in a vector space of dimension T , for some T ≥ 2. We notice that the PageRank algorithm can simply be viewed as a linear classifier in this vector space. In practice, no more than 3 steps are sufficient to attain most of PageRank's power on real networks [9], which suggests that the vector space can be of low dimension, say T = 2 or 3. Based on these observations, we propose some simple yet efficient versions of PageRank, like a parameter-free version called LexRank, consisting in ranking nodes according to the lexicographical order in the embedding space rather than to their PageRank values. Our main contribution is a novel algorithm, called WalkSCAN, that clusters the nodes in the embedding space using the popular DBSCAN algorithm [6].
A key feature of WalkSCAN is to output multiple communities, possibly overlapping. If the seed set S spreads over multiple communities, say ∪i∈I Ci, the clustering algorithm allows WalkSCAN to recover these different communities (Ci)i∈I , provided there are enough seed nodes in each of these communities. This is the main reason why WalkSCAN outperforms existing algorithms like PageRank on real networks, whose community structure is very complex [16] [7]. Moreover, our numerical results show that WalkSCAN is robust against errors, in the sense that it is generally able to recover the target community C even if the seed set S contains some nodes outside C.
The rest of the paper is organized as follows. In the next section, we describe the graph embedding based on random walks and the resulting algorithms, including LexRank and WalkSCAN. Some insights into the performance of these algorithms are provided in Section 3 through the theoretical analysis of the embedding on a toy network. The numerical experiments on real networks are presented in Section 4. Section 5 concludes the paper. The left figure shows a network with three communities A, B and C, where four seed nodes were picked in A (nodes in red). The right figure illustrates the result of the embedding using random walks of length 2 starting from the seed nodes. We see that nodes are mapped to three distinct zones in the embedding space that correspond to communities A, B and C.

ALGORITHMS
In this section, we first describe our graph embedding based on random walks starting from the seed set. We then use this embedding to revisit the properties of the PageRank algorithm and to propose two simple variants of this algorithm, namely PageRankThreshold and LexRank, as well as a novel algorithm, called WalkSCAN.

Graph embedding
Let G = (V, E) be an undirected graph. Nodes are assumed to be organized in communities, in the sense that nodes belonging to the same community tend to be more connected than with the rest of the graph [14]. The communities are unknown and the objective is to recover a target community C given some seed set S ⊂ C. We denote byĈ the output set.
A classical approach to this problem consists in using random walks starting from the seed set S. Specifically, we choose a node in S uniformly at random and walk in the graph choosing a neighbor of the current node uniformly at random. We use pt(v) to denote the probability for the walk to be in node v at time t. The vector p is initialized with p0(v) = 1S(v)/|S|, where 1S(v) = 1 if v ∈ S and 0 otherwise. Then, we have at any time t: where A denotes the adjacency matrix of the graph and d(u) = v Au,v the degree of node u. From these probabilities, we define a simple embedding that maps each node of v ∈ V to its random walk probabilities up to some specified time horizon T : The time horizon can be made very short to limit the exploration of the graph, say T = 2 or 3. It turns out that the graph embedding is meaningful even in this case. Taking T = 2 for instance, the respective probabilities for some node v to be reached after one and two steps should be much higher if v ∈ C. Thus we expect the different communities around the seed nodes to be mapped to distinct zones of the embedding space [0, 1] 2 , as illustrated by Figure 1.
By clustering the points in the embedding space, we should be able to recover the target community C. This is the idea of our algorithm WalkSCAN, described below. Before that, we revisit PageRank by interpreting it as a simple linear classifier in the embedding space and propose some simple yet efficient versions of this algorithm.

Understanding PageRank
The PageRank algorithm The PageRank algorithm is a classical algorithm for local community detection [9][21]. It is based on a random walk similar to that described above except that it goes to a neighbor of the current node with probability α and to a node chosen uniformly at random in the seed set S with probability 1 − α. The parameter α is known as the damping factor and is typically set to 0.85. This algorithm is sometimes referred to as personalized PageRank to make the difference with the original PageRank algorithm, corresponding to the case S = V . We use the simple name PageRank, as it is common in the literature.
Let rt(v) be the probability for the walk to be in node v at time t. The vector r is initialized by r0(v) = 1S(v)/|S| as before but now The PageRank algorithm ranks the nodes v by decreasing value of rT (v), for some given time horizon T . Let v k the node of rank k. A collection of sets is defined by S k = {v1, . . . , v k }, for all k such that rT (v k ) > 0. The algorithm then returns the best set S ∪ S k according to some scoring function f , that is the setĈ = S ∪ S k with This last step is called the sweep algorithm. Many different objective functions f can be used for this purpose [21], the most popular function being conductance [1]. Note that some algorithms order nodes by decreasing value of rT (v)/d(v) instead of rT (v). Theoretical guarantees are then available for the sweep algorithm [2] but the practical relevance of this modified version of PageRank has recently been questioned [9].

PageRank in the embedding space
It is straightforward to verify that the PageRank rT (v) of any node v ∈ S can be written Thus the PageRank algorithm has a direct interpretation in the embedding space; it returns the nodes v that are above the hyperplane of equation: for a parameter λ that maximizes the score function f. Considering the example of Figure 1 with T = 2, we see that, for some suitable values for the parameters α and λ, we are able to recover the target community by taking nodes above the line of equation: Note that the damping factor α characterizes the slope of this line. In particular, it allows one to control the respective weights of p1 and p2 in the PageRank value of each node: when α → 0, the line is vertical and only p1 is used whereas when α → 1, the line is horizontal only p2 is used. The default value α = 0.85 gives α/(1 − α) ≈ 5.7 more weight to p2 than to p1. The parameter λ depends on the local structure of the graph around the seed set S since it is chosen so as to maximize some score function, like the conductance.

Simplifying PageRank
Given the above observations, it is natural to propose the following simple variants of the PageRank algorithm.

PageRankThreshold
The first idea is to use some fixed threshold λ, which becomes a parameter of the algorithm. We refer to this algorithm as PageRankThreshold.
PageRankThreshold is much faster than PageRank, as it does not require to compute the score f (S ∪ S k ) for each k such that rT (v k ) > 0, the complexity of the score function being typically of the order of the total degree of the considered set. Of course, this leaves open the question of the choice of λ. However, in a semi-supervised learning setting where we have access to some ground-truth communities in the network, the optimal value for λ can be computed based on these ground-truth communities and used in the rest of the network. We implement this idea in Section 4.

LexRank
The second idea consists in keeping the objective function f but removing the damping factor α in order to make the PageRank algorithm parameter free (except for the time horizon T , typically set to T = 2 or 3). We then need to find a ranking of the nodes in order to apply the sweep algorithm. Recall that in PageRank with T = 2 and α = 0.85, the sweep algorithm boils down to a linear separation of the points (p1(v), p2(v)), where p2(v) is given more weight than p1(v). It can be argued that p1(v) (positive for neighbors of the seed nodes) should actually be given more weight than p2(v). We give it the highest weight by applying the lexicographical order 1 in the embedding space. We refer to this algorithm as LexRank.
In words, LexRank first compares the probabilities p1(v) to be at one step from the seed set, then the probabilities p2(v) to be at two steps from the seed set, and so on, whereas PageRank compares linear combinations of these probabilities, with weights depending on the damping factor.

WalkSCAN
We now define our local community detection algorithm, called WalkSCAN, which fully exploits the graph embedding v → p(v) defined above. A clear limitation of PageRank is the use of a linear classifier to cluster nodes in the embedding space. The idea of WalkSCAN is to group nodes that are close to each other in the embedding space. In particular, WalkSCAN may output multiple communities, possibly overlapping, and thus reveal the complex community structure of the graph. These communities are considered in reverse lexicographical order on their mean value in the embedding space, the first community in this order being the more relevant.
To be more precise, let K1, . . . , KJ be the connected components of size at least 2 in the graph G = (V , E ) defined by: where d > 0 is a distance parameter, and · is the euclidean norm. Hence, two nodes u and v are in the same connected component Kj if and only if there exists a path between u and v of points that are within distance d of each other in the embedding space. We also define the set of outliers O as the set of nodes of V that do not belong to any set K1, . . . , KJ . Note that this approach is a special case of the popular clustering algorithm DBSCAN [7] with parameters = d and minSize=2. Each component Kj is the core of some communityĈj, which is obtained from Kj by adding the outliers having at least one neighbor in Kj in the original graph G. Note that whereas the sets Kj are disjoints, an outlier can have neighbors in different community cores, so that WalkSCAN may output overlapping communities. 1 u ≺ v for this order if for some s ∈ {1, ..., T }, pt(u) = pt(v) for all t < s and ps(u) < ps(v).

ANALYSIS
In this section, we show on a toy network consisting of overlapping cliques that clusters of nodes in the embedding space correspond to these cliques, even in the simplest case where T = 2. We demonstrate that this property still holds when we add noise to the model, and deduce some insights into the behavior of our algorithms. Then, we qualitatively compare the results obtained in the analysis to observations in a real-world network.

Embedding of a toy network
Overlapping cliques First, we consider the case of two overlapping cliques isolated from the rest of the graph. Let V be a set of nodes, and C1 and C2 be two subsets of V such that C1 ∩ C2 = ∅. We assume that C1 and C2 form cliques and are disconnected from V \ (C1 ∪ C2). The adjacency matrix A of the graph satisfies: Assume that C1 is the target community and that S ⊂ C1, with S ∩ (C1 \ C2) = ∅. We take T = 2 for simplicity; the analysis can be easily extended to the case T ≥ 3. We show in Appendix A that there exists three vectors p1∩2, p 1\2 and p 2\1 in R 2 such that, for all v ∈ V \ S, These vectors satisfy p1∩2 ≥ p 1\2 , p 2\1 componentwise so that both PageRank and PageRankThreshold would recover either C1 ∩ C2, C1 or C2, or C1 ∪ C2, depending on the sweep algorithm or the threshold λ, the output C1 or C2 depending on the damping factor α and the respective sizes of these communities compared to their intersection. Since p1∩2 p 1\2 p 2\1 for the lexicographical order, LexRank will always recover either C1 ∩ C2, C1 or C1 ∪ C2, depending on the sweep algorithm, which suggests that this algorithm is less sensitive to the respective sizes of the communities.

Now defining
we have d1 < d2 if |S ∩ C1 ∩ C2| is small enough compared to |S ∩ (C1 \ C2)| (see Appendix A). If the distance parameter of WalkSCAN satisfies d < d1 < d2, we have three core sets corresponding to C1 ∩ C2, C1 \ C2 and C2 \ C1, and the two communities C1 and C2 can be fully recovered: WalkSCAN outputs C1 ∩ C2, C1 \ C2 and C2 \ C1 in this order, which allows to recover both communitites C1, C2 and their intersection. If d1 < d < d2, we have two core sets corresponding to C1 and C2 \C1 and WalkSCAN will output C1 and C2 \C1 in this order. Next, we study a more realistic model obtained by removing edges in the cliques or by adding edges between C1 ∪ C2 and V \ (C1 ∪ C2).

From cliques to quasi-cliques
Consider a model where k edges are removed from C1 or C2, which is more representative of real-world networks where communities are dense sets but not cliques in general. Assume that S ⊂ C1 \ C2. Denoting byp(v) the initial graph embedding, without removing these edges, we show in Appendix B that for all nodes v but k in the worst case scenario, provided k is small enough compared to |C1|. Thus, if the distance parameter of WalkSCAN satisfies d1 < d < d2, where d1 and d2 are defined by (1)-(2) (for the cliques), the algorithm will output C1 and C2 \ C1 in this order.

Adding external links
Now consider the two-clique model where l edges are added between nodes of C1 ∪ C2 and nodes of V \ (C1 ∪ C2). We show in Appendix C that provided |C1|/l is large enough. Thus, if d1 < d < d2, WalkSCAN will output C1 and C2 \ C1 in this order.

Embedding of a real-world network
In Figure 2, we plot the embedding (p1(v), p2(v)) of the DBLP graph for a seed set S consisting of two nodes in a given ground-truth community, say C1 (see Section 4 for details on the dataset). One of these nodes belongs to another community C2. We observe groups of nodes sharing the same feature values in the embedding space, represented by disks, and nodes with singular values in the embedding space, represented by triangles.
The results correspond qualitatively to the above analysis. Depending on the sweep algorithm or the threshold λ, PageRank, PageRankThreshold and LexRank will approximately output either C1 ∩ C2, C1 or C1 ∪ C2, LexRank being more efficient for identifying C2 \ C1. By clustering points in the embedding space, WalkSCAN is able to recover the complete community structure, namely C1, C2 and their intersection, up to some isolated points, depending on the distance parameter d.

EXPERIMENTAL RESULTS
We now analyse the performance of our algorithms through numerical experiments on real networks.

Datasets
We use two datasets of real networks available from the Stanford Social Network Analysis Project (SNAP) [21]: DBLP (graph of co-authorship) and YouTube (online social graph). These datasets, whose main features are given in Table 1, include ground-truth community memberships that we use to measure the quality of the results. We use the top 5000 communities in each of these datasets for our benchmarks.   corroborates the results of [9] concerning PageRank. For WalkSCAN, we take T = 2, which turns out to provide the best results (although the results are very similar for T = 3).
Note that we do not included LEMON [12] and Heat Kernel [8] in our benchmark because our experiments have shown that they never outperform PageRank.

Performance metric
We use the F1-Score to evaluate the performance of the algorithms. The F1-Score F1(Ĉ, C) of the outputĈ for the target community C is the harmonic mean of the precision and the recall ofĈ with respect to C:

Recovering a single community
For each dataset and each ground-truth community C, we choose a random subset S of C of size |C|/10 as the seed set and compute the F1 score of each algorithm. The results are averaged over the N ground-truth communities (recall that we take N = 5000 for each dataset).
A basic approach to assess the performance of WalkSCAN is to consider only the first community returned by the algorithm. This is a bit restrictive, however, since valuable information can be retrieved from the other communities returned by the algorithm. If we have access to some experts for instance, one may submit the first K communities returned by WalkSCAN to these experts and let them choose the best one among these. This is equivalent to computing the maximum of F1(Ĉj, C) for the K first communitiesĈj returned by WalkSCAN. We denote the corresponding algorithm by WS-Expert (WalkSCAN helped by Experts). In practice, K can be very small. Here, we use K = 2, and observe that the performance shows pratically no increase for higher values of K. Figure 3 shows the results for DBLP and YouTube. We notice that both WS and WS-Expert show better results than PR. In particular, WS-Expert outperforms PR by 13% on YouTube and by 5% on DBLP. PRT slightly outperforms PR but the results cannot be compared directly since PRT uses some information on the network (to determine the best threshold λ). However, the results suggest that conductance is not the best objective function for the sweep algorithm, and that a simple threshold on the PageRank values is preferable. LR shows essentially the same performance as PR, with the advantage of being parameter free. Figure 4 shows the impact of the distance parameter d on the performance of WalkSCAN. We observe that the average detection score of WS-Expert is nearly constant for values of d lower than 0.1, whereas the performance of WS increases notably around d = 0.4. This behavior is consistent with the results of the analysis from the previous section. Recall that WS only considers the communityĈ1, whereas WS-Expert choses the best community amongĈ1, ...,ĈK . When d < d1 < d2 in our simple model,Ĉ1 corresponds to C1 ∩ C2 andĈ2 to C1 \ C2. Then WS returns C1 ∩ C2, whereas WS-Expert returns C1 \ C2, which leads to a better F1 score. If d1 < d < d2,Ĉ1 corresponds to C1, and both WS and WS-Expert return C1. This explains why the detection score of WS is more sensitive to the value of d than WS-Expert.

Merging communities: WS-Merge
We now study the performance gain achieved when the expert of WS-Expert is allowed to merge two communities. This is equivalent to computing the maximum of F1(Ĉj, C) and F1(Ĉi ∩Ĉj, C) among the K first communities returned by WalkSCAN. We refer to this modified version of Walk-SCAN as WS-Merge. In the two-clique model of §3.1, WS-Merge would output C1 whereas WS would output either C1 ∩ C2 or C1. The results given in Figure 5 show that WS-Merge outperforms WS-Expert (this increase is especially noticeable on DBLP). In the end, the average F1 score of WS-Merge is 11% higher on DBLP, and 14% higher on YouTube, than the one of PageRank. This can be explained by the fact that ground-truth communities in the SNAP datasets can often be decomposed into sub-communities [7]. WalkSCAN sometimes recovers these sub-communities rather than the ground-truth community as labeled in the dataset. This raises the important question of the multi-scale community structure of real networks. There is no universal definition of a community, just because this depends implicitely on the scale adopted. We believe that WalkSCAN is an important step towards the multi-scale analysis of communities in networks. The following experiments illustrate the ablity of WalkSCAN to detect multiple communities.

Recovering multiple communities
A motivating example If our seed set contains nodes from different communities, or if one or more seed nodes belong simultaneously to several overlapping communities, standard algorithms like PageRank are generally not able to recover all these communities. This is an important limitation as in real networks, each community has many other communities in its neighborhood, and these communities are very likely to overlap. If we consider that seed nodes are recommended by domain experts [9], these experts might very well make some mistakes and propose nodes outside the target community, or recommend nodes that belong to the target community and a neighboring community at the same time. We would like to be able to recover the correct community even if we have such mixed seed sets. In the two-clique model of §3.1, this would correspond to some seed set S ⊂ C1 ∪ C2. It can be easily checked that the complete community structure (C1, C2 and their intersection) can still be recovered by WalkSCAN provided the proportion of seed nodes in the intersection is sufficiently small (otherwise, only C1 ∩ C2 or C1 ∪ C2 is recovered).
In the following benchmarks, we test on real networks the ability of WalkSCAN to recover the correct communities when the seed nodes belong to more than one community.

Random seed set
For any given integer k ≥ 1, we take random sets S ⊂ V of size k as seed sets. The target community is the union of all communities to which these seed nodes belong. We compare the performance of PageRank (with the conductance as objective function) and WalkSCAN, where the estimated community correponds to the merging of all the communi-tiesĈj returned by the algorithm. The results are shown in Figure 6 for the DBLP dataset and 1000 independent runs per value of k. We see that the performance of PR drops significantly faster than that of WS as k increases.

Locally random seed set
In practice, experts do not choose completely random seed nodes in V , but nodes around a target community. Here, we consider a more realistic setup where given some groundtruth community C, we pick |C|/10 nodes at random in C or at distance at most l of C. The results are averaged over all ground-truth communities of the dataset. We use WS-Expert to measure the performance of WalkSCAN, which is consistent with the choice of the seed set. The results are shown in Figure 7 for the DBLP dataset. Again, WS-Expert outperforms PR significantly.

CONCLUSION
In this paper, we have introduced an embedding of the local structure of the network into a low-dimensional vector space based on random walks starting from the seed nodes. We have seen both theoretically on a clique-based model and experimentally on real-world networks that this embedding has very interesting properties for detecting communities in the neighborhood of the seed set. Indeed, nodes belonging to different communities in the network are well separated in the embedding space.
Building on this embedding, we have designed a new algorithm, called WalkSCAN, that outperforms the state-ofthe-art PageRank algorithm on real data and is able to recover multiple communities in the neighborhood of the seed nodes. WalkSCAN is therefore more adapted to real cases where we do not necessarily control the quality of the seed set, in the sense that seeds are likely to belong to multiple communities. The random-walk embedding also gives insights on the behavior of the PageRank algorithm, which can be viewed as a linear classifier in the embedding space. From these observations, we have introduced two variants of PageRank, PageRankThreshold and LexRank, that slightly outperform PageRank on real networks: PageRankThreshold has the advantage not to depend on a computationally expensive objective function, while LexRank is parameter-free.
This work opens interesting research directions. First, we would like to study the possibility of using cores as new seed sets for seed set expansion algorithms. This re-seeding strategy could be used to improve WalkSCAN, or could be applied to the detection of overlapping communities. Second, we plan to explore the potential benefits of adding node attributes or edge attributes as new dimensions of the embedding to perform community detection on annotated networks. Finally, we would like to explore the interest of our embedding to other contexts like network visualization and link prediction.

A. OVERLAPPING CLIQUES
Consider two overlapping cliques C1 and C2, as described in §3.1.

Single seed node
We first assume that the seed set is reduced to a single node, say S = {v0}.
We have: We have: otherwise.

General case
In the general case where there may be more than one seed node, we get: where a = |S ∩ (C1 \ C2)| and b = |S ∩ (C1 ∩ C2)|. Observe that p1∩2 p 1\2 p 2\1 for the lexicographical order. In addition, the distances between points in the embedding space are given by: In particular, we have d1 < d2 if a/b is large enough.