刚刚开始接触community detection相关的内容，在找资料和了解相关定义、算法的过程中发现自己的记录很混乱，所以借此记录下自己的一些学习过程，希望可以一起学习交流。
首先咱们来讨论一下文献查找，本文主要列出了机器学习、数据挖掘和人工智能领域的相关文献，我是直接搜索这些领域的相关会议，然后找到accepted papers，利用关键词（community）进行文章的查找和整理，当然也可以直接在百度学术、必应学术、谷歌学术等一系列搜索引擎中或者dblp之类的数据库利用关键词查找。其实深以为自己这样的查找方式有点低效，得一篇篇地看摘要，了解讲的啥才能知道是不是自己要找的文献，但是好像也没有更加高效的方法，毕竟要自己一步一步地去做，才能更了解。（所以我也不知道自己在说啥。。。）
好啦！现在来看看我选择的会议吧：
- 机器学习（NIPS, ICML, ECML, COLT）
- 数据挖掘（SIGKDD, ICDM, PAKDD, SDM, PKDD）
- 人工智能（IJCAI, AAAI）
这些会议是相关领域内一些比较重要的会议，当然还有许多非常好的会议，我这边列得不全，可以自行查找。
文章列表
- 机器学习
Community Detection on Evolving Graphs,NIPS2016
”In this paper, we study a model of clustering on evolving graphs that captures this aspect of the problem. Our model is based on the classical stochastic block model, which has been used to assess rigorously the quality of various static clustering methods. In our model, the algorithm is supposed to reconstruct the planted clustering, given the ability to query for small pieces of local information about the graph, at a limited rate. ”
Community Detection via Measure Space Embedding,NIPS2015
”We present a new algorithm for community detection. The algorithm uses random walks to embed the graph in a space of measures, after which a modification of k-means in that space is applied. ”“We evaluate the algorithm on standard random graph benchmarks, including some overlapping community benchmarks.”
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models,ICML2018
However, modeling complex distributions over graphs and then efficiently sampling from these distributions is challenging due to the non-unique, high-dimensional nature of graphs and the complex, non-local dependencies that exist between edges in a given graph. Here we propose GraphRNN, a deep autoregressive model that addresses the above challenges and approximates any distribution of graphs with minimal assumptions about their structure. GraphRNN learns to generate graphs by training on a representative set of graphs and decomposes the graph generation process into a sequence of node and edge formations, conditioned on the graph structure generated so far.
Community Recovery in Graphs with Locality,ICML2016
“we study the problem of community recovery in graphs with locality. In this problem, pairwise noisy measurements of whether two nodes are in the same community or different communities come mainly or exclusively from nearby nodes rather than uniformly sampled between all node pairs, as in most existing models. We present two algorithms that run nearly linearly in the number of measurements and which achieve the information limits for exact recovery. ”
Community Detection Using Time-Dependent Personalized PageRank, ICML2015
“ We present an efficient local algorithm for approximating a graph diffusion that generalizes both the celebrated personalized PageRank and its recent competitor/companion - the heat kernel. Our algorithm is based on writing the diffusion vector as the solution of an initial value problem, and then using a waveform relaxation approach to approximate the solution. ”
“ Burer and Monteiro proposed a heuristic to solve such semi definite programs by restricting the search space to low-rank matrices. The accompanying theory does not explain the extent of the empirical success. We focus on Synchronization and Community Detection problems and provide theoretical guarantees shedding light on the remarkable efficiency of this heuristic. ”
“In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with k blocks, for any k fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.”
Computational Lower Bounds for Community Detection on Random Graphs,COLT2015
“ This paper studies the problem of detecting the presence of a small dense community planted in a large Erdos-Renyi random graph G(N, q). ”
数据挖掘
Inferring the Strength of Social Ties: A Community-Driven Approach, KDD2017
“ To guide our inference process, in addition to the network structure, we also consider as input a collection of tight communities. Those are sets of vertices that we expect to be connected via strong ties. Such communities appear in different situations, e.g., when being part of a community implies a strong connection to one of the existing members.”
Joint Community and Structural Hole Spanner Detection via Harmonic Modularity,KDD2016
“ Detecting communities (or modular structures) and structural hole spanners, the nodes bridging different communities in a network, are two essential tasks in the realm of network analytics. … In this paper, we propose a novel harmonic modularity method to tackle both tasks simultaneously. ”
Community Detection based on Distance Dynamics,KDD2015
“ In this paper, we introduce a new community detection algorithm, called Attractor, which automatically spots communities in a network by examining the changes of “distances” among nodes (i.e. distance dynamics). ”
Probabilistic Community and Role Model for Social Networks,KDD2015
“ In this paper, we propose a unified probabilistic framework, the Community Role Model (CRM), to model a social network. CRM incorporates all the information of nodes and edges that form a social network. We propose methods based on Gibbs sampling and an EM algorithm to estimate the model’s parameters and fit our model to real social networks. ”
Many Heads are Better than One: Local Community Detection by the Multi-Walker Chain,ICDM2017
In this paper, we study a multi-walker chain (MWC) model, which allows multiple walkers to explore the network. Each walker is influenced (or pulled back) by all other walkers when deciding the next steps. This helps the walkers to stay as a group and within the cluster. We introduce two measures based on the mean and standard deviation of the visiting probabilities of the walkers. These measures not only can accurately identify the local cluster, but also help detect the cluster center and boundary, which cannot be achieved by the existing single-walker methods.
Revisiting Spectral Graph Clustering with Generative Community Models,ICDM2017
“ The presented method, SGC-GEN, not only considers the detection error caused by the corresponding model mismatch to a given graph, but also yields a theoretical guarantee on community detectability by analyzing Spectral Graph Clustering (SGC) under GENerative community models (GCMs). ”“ We further establish a theoretical condition for correct community detection using the normalized graph Laplacian matrix under a GCM, which provides a novel data-driven loss function for SGC-GEN. ”
Overlapping Community Detection via Constrained PARAFAC: A Divide and Conquer Approach,ICDM2017
The present work puts forward a top-to-bottom community identification approach, termed DC-EgoTen, in which an egonet-tensor (EgoTen) based algorithm is developed in a divide-and-conquer (DC) fashion for breaking the network into smaller subgraphs, out of which the underlying communities progressively emerge. In particular, each step of DC-EgoTen forms a multi-dimensional egonet-based representation of the graph, whose induced structure enables casting the task of overlapping community identification as a constrained PARAFAC decomposition. Thanks to the higher representational capacity of tensors, the novel egonet-based representation improves the quality of detected communities by capturing multi-hop connectivity patterns of the network. In addition, the top-to-bottom approach ensures successive refinement of identified communities, so that the desired resolution is achieved.
Local Community Detection in Dynamic Networks,ICDM2017
“ We propose a filter-and-verify framework for dynamic community detection. To scale to long intervals of graph evolution, we employ novel spectral bounds for dynamic community conductance and employ them to filter suboptimal periods in near-linear time. We also design a time-and-graph-aware locality sensitive hashing family to effectively spot promising community cores. ”
Community Detection Based on Structure and Content: A Content Propagation Perspective,ICDM2015
“ In this paper we combine the topological structure of a network as well as the content information of nodes in the task of detecting communities in information networks. Specifically, we treat a network as a dynamic system and consider its community structure as a consequence of interactions among nodes. To model the interactions we introduce the principle of content propagation and integrate the aspects of structure and content in a network naturally. We further describe the interactions among nodes in two different ways, including a linear model to approximate influence propagation, and modeling the interactions directly with random walk. ”
Manifold Regularized Symmetric Joint Link Model for Overlapping Community Detection,PAKDD2015
“ we propose a Manifold Regularized Symmetric Joint Link Model (MSJL), which utilizes the local geometrical structure of manifold to improve the performance of overlapping community detection. MSJL assumes that the community probability distribution lives on a submanifold, and adopts the manifold assumption which specifically requires two close nodes in an intrinsic geometry to have similar community distribution. The structure of the intrinsic manifold is modeled by a nearest neighbor graph, and MSJL incorporates the graph Laplacian as a manifold regularization into the maximum likelihood function of the standard SJL model. ”
人工智能
Modularity Based Community Detection with Deep Learning, IJCAI2016
“ we propose a novel nonlinear reconstruction method by adopting deep neural networks for representation. We then extend the method to a semi-supervised community detection algorithm by incorporating pairwise constraints among graph nodes ”
“ In this paper, we propose a Homophily-based Nonnegative Matrix Factorization (HNMF) to model both-sided relationships between links and communities. From the community-to-link perspective, we apply a preference-based pairwise function by assuming that nodes with common communities have a higher probability to build links than those without common communities. From the link-to-community perspective, we propose a new community representation learning with network embedding by assuming that linked nodes have similar community representations. ”
A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models,IJCAI2015
“ In this paper, we propose a multi-stage maximum likelihood approach to recover the latent parameters of the stochastic block model, in time linear with respect to the number of edges. We also propose a parallel algorithm based on message passing. ”
Exploiting k-degree locality to improve overlapping community detection,IJCAI2015
“ In this paper, we propose a Locality-based Non-negative Matrix Factorization (LNMF) model to refine a preference-based model by incorporating locality into learning objective.We define a subgraph called “k-degree local network” to set a boundary between local non-neighbors and other non-neighbors. ”
“ In this paper, we construct a new measure of similarity between nodes based on the game-theoretic interaction index (Grabisch and Roubens, 1997). Despite the fact that, in general, this index is computationally challenging, we show that in our network application it can be computed in polynomial time. ”
**备注：
- 点击文章标题可跳转至pdf界面
- 文章中未列出的会议时间即表示这个时间点无相关文献
- 或许会有遗漏和错误，欢迎补充和提出！
- 每篇文章都给出了我认为比较重要的摘要，大概能概括这篇文章。
- 我正在看其中的几篇，有机会会贴出自己的学习笔记，欢迎一起交流学习。