Local Algorithms for Finding Densely Connected Clusters
Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset.
Code (1)
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
On the Brain Networks of Complex Problem Solving
Complex problem solving is a high level cognitive process which has been thoroughly studied over the last decade. The Tower of London (TOL) is a task that has been widely used to study problem-solving. In this study, we …
DCC: A Cascade based Approach to Detect Communities in Social Networks
Community detection in Social Networks is associated with finding and grouping the most similar nodes inherent in the network. These similar nodes are identified by computing tie strength. Stronger ties indicates higher …
Community DetectionRelative Depth Order Estimation Using Multi-scale Densely Connected Convolutional Networks
We study the problem of estimating the relative depth order of point pairs in a monocular image. Recent advances mainly focus on using deep convolutional neural networks (DCNNs) to learn and infer the ordinal information…
Densely Connected Residual Network for Attack Recognition
High false alarm rate and low detection rate are the major sticking points for unknown threat perception. To address the problems, in the paper, we present a densely connected residual network (Densely-ResNet) for attack…
Sparsity-aware Robust Community Detection(SPARCODE)
Community detection refers to finding densely connected groups of nodes in graphs. In important applications, such as cluster analysis and network modelling, the graph is sparse but outliers and heavy-tailed noise may ob…
Community Detection