Provable Overlapping Community Detection in Weighted Graphs

• URL: http://arxiv.org/abs/2004.07150v2
• Date: Sun, 19 Apr 2020 17:42:13 GMT
• Title: Provable Overlapping Community Detection in Weighted Graphs
• Authors: Jimit Majmudar, Stephen Vavasis
• Abstract summary: We provide a provable method to detect overlapping communities in weighted graphs without explicitly making the pure nodes assumption. Our approach is based on convex optimization, for which many useful theoretical properties are already known. We demonstrate the success of our algorithm on artificial and real-world datasets.
• Score: 3.04585143845864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a widely-studied unsupervised learning problem in which the task is to group similar entities together based on observed pairwise entity interactions. This problem has applications in diverse domains such as social network analysis and computational biology. There is a significant amount of literature studying this problem under the assumption that the communities do not overlap. When the communities are allowed to overlap, often a pure nodes assumption is made, i.e. each community has a node that belongs exclusively to that community. This assumption, however, may not always be satisfied in practice. In this paper, we provide a provable method to detect overlapping communities in weighted graphs without explicitly making the pure nodes assumption. Moreover, contrary to most existing algorithms, our approach is based on convex optimization, for which many useful theoretical properties are already known. We demonstrate the success of our algorithm on artificial and real-world datasets.

Related papers

• Enhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms [49.1574468325115]
  This study employs the same method to evaluate the relevance of using local similarity metrics for community detection. The efficacy of these metrics was evaluated by applying the base algorithm to several real networks with varying community sizes.
  arXiv  Detail & Related papers  (2024-08-17T02:17:09Z)
• A multi-core periphery perspective: Ranking via relative centrality [4.33459568143131]
  Community and core-periphery are two widely studied graph structures. The impact of inferring the core-periphery structure of a graph on understanding its community structure is not well utilized. We introduce a novel for graphs with ground truth communities, where each community has a densely connected part (the core) and the rest is more sparse (the periphery)
  arXiv  Detail & Related papers  (2024-06-06T20:21:27Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  We study a semi-supervised community detection problem in which the objective is to estimate the community label of a new node. We propose an algorithm that computes a structural similarity metric' between the new node and each of the $K$ communities. Our findings highlight, to the best of our knowledge, the first semi-supervised community detection algorithm that offers theoretical guarantees.
  arXiv  Detail & Related papers  (2023-06-01T19:02:50Z)
• Is it easier to count communities than find them? [82.90505487525533]
  We consider certain hypothesis testing problems between models with different community structures. We show that testing between two options is as hard as finding the communities.
  arXiv  Detail & Related papers  (2022-12-21T09:35:19Z)
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection [0.0]
  Community detection aims to partition a network into clusters of nodes to summarize its large-scale structure. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model. Other methods are descriptive, dividing a network according to an objective motivated by a particular application. We present a solution that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model.
  arXiv  Detail & Related papers  (2022-10-17T15:38:41Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• QD-GCN: Query-Driven Graph Convolutional Networks for Attributed Community Search [54.42038098426504]
  QD-GCN is an end-to-end framework that unifies the community structure as well as node attributes to solve the ACS problem. We show that QD-GCN outperforms existing attributed community search algorithms in terms of both efficiency and effectiveness.
  arXiv  Detail & Related papers  (2021-04-08T07:52:48Z)
• Variational Embeddings for Community Detection and Node Representation [5.197034517903854]
  We propose an efficient generative model called VECoDeR for jointly learning Variational Embeddings for Community Detection and node Representation. We demonstrate on several graph datasets that VECoDeR effectively out-performs many competitive baselines on all three tasks.
  arXiv  Detail & Related papers  (2021-01-11T13:36:29Z)
• Mixed Membership Graph Clustering via Systematic Edge Query [22.77704627076251]
  This work considers clustering nodes of a largely incomplete graph. Under the problem setting, only a small amount of queries about the edges can be made, but the entire graph is not observable. This problem finds applications in large-scale data clustering using limited annotations, community detection under restricted survey resources, and graph topology inference.
  arXiv  Detail & Related papers  (2020-11-25T19:19:05Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)
• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing [81.71105567425275]
  We develop the first certified robustness guarantee of community detection against adversarial structural perturbation. We theoretically show that the smoothed community detection method provably groups a given arbitrary set of nodes into the same community. We also empirically evaluate our method on multiple real-world graphs with ground truth communities.
  arXiv  Detail & Related papers  (2020-02-09T18:39:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.