Based on the definition of local spectral subspace, we propose a novel approach called LOSP for local overlapping community detection. Using the power method for a few steps, LOSP finds an approximate invariant subspace, which depicts the embedding of the local neighborhood structure around the seeds of interest. LOSP then identifies the local community expanded from the given seeds by seeking a sparse indicator vector in the subspace where the seeds are in its support. We provide a systematic investigation on LOSP, and thoroughly evaluate it on large real world networks across multiple domains. With the prior information of very few seed members, LOSP can detect the remaining members of a target community with high accuracy. Experiments demonstrate that LOSP outperforms the Heat Kernel and PageRank diffusions. Using LOSP as a subroutine, we further address the problem of multiple membership identification, which aims to find all the communities a single vertex belongs to. High F1 scores are achieved in detecting multiple local communities with respect to arbitrary single seed for various large real world networks.
There are also other local methods based on the random walk technique. For instance, Wu et. al @cite_2 use a variant of the degree normalized, penalized hitting probability to weight the nodes by starting from the query nodes, and define the reciprocal of the weight as the query biased density to effectively reduce the free rider effect that tends to include irrelevant subgraphs in the detected local community. All seed set expansion methods need a stopping criterion for defining the community boundary unless the size of the target community is known. Conductance is commonly recognized as the best stopping criterion due to its intrinsic local property @cite_14 @cite_10 @cite_8 . Yang and Leskovec provide widely-used real world datasets with labeled ground truth @cite_8 , and find that conductance and triad-partition-ratio (TPR) are the two stopping rules yielding the highest detection accuracy. The Heat Kernel method also adopts conductance as the stopping rule for the local community @cite_14 .
@cite_8 @cite_14 @cite_10 @cite_2
2207622687 2275798569 2142385580 2003804278
Given a large network, local community detection aims at finding the community that contains a set of query nodes and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. Various goodness metrics have been proposed. However, most existing metrics tend to include irrelevant subgraphs in the detected local community. We refer to such irrelevant subgraphs as free riders. We systematically study the existing goodness metrics and provide theoretical explanations on why they may cause the free rider effect. We further develop a query biased node weighting scheme to reduce the free rider effect. In particular, each node is weighted by its proximity to the query node. We define a query biased density metric to integrate the edge and node weights. The query biased densest subgraph, which has the largest query biased density, will shift to the neighborhood of the query nodes after node weighting. We then formulate the query biased densest connected subgraph (QDC) problem, study its complexity, and provide efficient algorithms to solve it. We perform extensive experiments on a variety of real and synthetic networks to evaluate the effectiveness and efficiency of the proposed methods. In local community detection by seed expansion a single cluster concentrated around few given query nodes in a graph is discovered in a localized way. Conductance is a popular objective function used in many algorithms for local community detection. Algorithms that directly optimize conductance usually add or remove one node at a time to find a local optimum. This amounts to fix a specific neighborhood structure over clusters. A natural way to avoid the problem of choosing a specific neighborhood structure is to use a continuous relaxation of conductance. This paper studies such a continuous relaxation of conductance. We show that in this setting continuous optimization leads to hard clusters. We investigate the relation of conductance with weighted kernel k-means for a single cluster, which leads to the introduction of a weighted kernel 1-mean objective function, called -conductance, where is a parameter which influences the size of the community. Conductance is obtained by setting to 0. Two algorithms for local optimization of -conductance based on the expectation maximization and the projected gradient descend method are developed, called EMc and PGDc, respectively. We show that for =0 EMc corresponds to gradient descend with an infinite step size at each iteration. We design a procedure to automatically select a value for . Performance guarantee for these algorithms is proven for a class of dense communities centered around the seeds and well separated from the rest of the network. On this class we also prove that our algorithms stay localized. A comparative experimental analysis on networks with ground-truth communities is performed using state-of-the-art algorithms based on the graph diffusion method. Our experiments indicate that EMc and PGDc stay localized and produce communities most similar to the ground. We propose a novel approach to performing efficient similarity search and classification in high dimensional data. In this framework, the database elements are vectors in a Euclidean space. Given a query vector in the same space, the goal is to find elements of the database that are similar to the query. In our approach, a small number of independent "voters" rank the database elements based on similarity to the query. These rankings are then combined by a highly efficient aggregation algorithm. Our methodology leads both to techniques for computing approximate nearest neighbors and to a conceptually rich alternative to nearest neighbors.One instantiation of our methodology is as follows. Each voter projects all the vectors (database elements and the query) on a random line (different for each voter), and ranks the database elements based on the proximity of the projections to the projection of the query. The aggregation rule picks the database element that has the best median rank. This combination has several appealing features. On the theoretical side, we prove that with high probability, it produces a result that is a (1 + e) factor approximation to the Euclidean nearest neighbor. On the practical side, it turns out to be extremely efficient, often exploring no more than 5 of the data to obtain very high-quality results. This method is also database-friendly, in that it accesses data primarily in a pre-defined order without random accesses, and, unlike other methods for approximate nearest neighbors, requires almost no extra storage. Also, we extend our approach to deal with the k nearest neighbors.We conduct two sets of experiments to evaluate the efficacy of our methods. Our experiments include two scenarios where nearest neighbors are typically employed---similarity search and classification problems. In both cases, we study the performance of our methods with respect to several evaluation criteria, and conclude that they are uniformly excellent, both in terms of quality of results and in terms of efficiency. Focusing on the problems of over-specialization and concentration bias, this paper presents a novel probabilistic method for recommending items in the neighborhood-based collaborative filtering framework. For the probabilistic neighborhood selection phase, we use an efficient method for weighted sampling of k neighbors that takes into consideration the similarity levels between the target user (or item) and the candidate neighbors. We conduct an empirical study showing that the proposed method increases the coverage, dispersion, and diversity reinforcement of recommendations by selecting diverse sets of representative neighbors. We also demonstrate that the proposed approach outperforms popular methods in terms of item prediction accuracy, utility-based ranking, and other popular measures, across various experimental settings. This performance improvement is in accordance with ensemble learning theory and the phenomenon of "hubness" in recommender systems.