Sketch-based community detection in evolving networks

• URL: http://arxiv.org/abs/2009.11835v1
• Date: Thu, 24 Sep 2020 17:32:57 GMT
• Title: Sketch-based community detection in evolving networks
• Authors: Andre Beckus and George K. Atia
• Abstract summary: We consider an approach for community detection in time-varying networks. At its core, this approach maintains a small sketch graph to capture the essential community structure found in each snapshot of the full network. We formulate a community detection algorithm which can process a network concurrently exhibiting all processes.
• Score: 15.512086254435788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an approach for community detection in time-varying networks. At its core, this approach maintains a small sketch graph to capture the essential community structure found in each snapshot of the full network. We demonstrate how the sketch can be used to explicitly identify six key community events which typically occur during network evolution: growth, shrinkage, merging, splitting, birth and death. Based on these detection techniques, we formulate a community detection algorithm which can process a network concurrently exhibiting all processes. One advantage afforded by the sketch-based algorithm is the efficient handling of large networks. Whereas detecting events in the full graph may be computationally expensive, the small size of the sketch allows changes to be quickly assessed. A second advantage occurs in networks containing clusters of disproportionate size. The sketch is constructed such that there is equal representation of each cluster, thus reducing the possibility that the small clusters are lost in the estimate. We present a new standardized benchmark based on the stochastic block model which models the addition and deletion of nodes, as well as the birth and death of communities. When coupled with existing benchmarks, this new benchmark provides a comprehensive suite of tests encompassing all six community events. We provide a set of numerical results demonstrating the advantages of our approach both in run time and in the handling of small clusters.

Related papers

• Sifting out communities in large sparse networks [2.666294200266662]
  We introduce an intuitive objective function for quantifying the quality of clustering results in large sparse networks. We utilize a two-step method for identifying communities which is especially well-suited for this domain. We identify complex genetic interactions in large-scale networks comprised of tens of thousands of nodes.
  arXiv  Detail & Related papers  (2024-05-01T18:57:41Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• 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)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  We rigorously understand the performance of two major algorithms, DeepWalk and node2vec, in recovering communities for canonical network models. We prove that, given some fixed co-occurrence window, node2vec using random walks with a low non-backtracking probability can succeed for much sparser networks.
  arXiv  Detail & Related papers  (2021-11-04T14:57:43Z)
• Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
  Domain-adaptive hash learning has enjoyed considerable success in the computer vision community. We develop an unsupervised domain-adaptive hash learning method for networks, dubbed UDAH.
  arXiv  Detail & Related papers  (2021-08-20T12:09:38Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)
• Community detection in networks using graph embeddings [0.615738282053772]
  We test the ability of several graph embedding techniques to detect communities on benchmark graphs. We find that the performance is comparable, if the parameters of the embedding techniques are suitably chosen. This finding, along with the high computational cost of embedding a network and grouping the points, suggests that, for community detection, current embedding techniques do not represent an improvement over network clustering algorithms.
  arXiv  Detail & Related papers  (2020-09-11T07:49:21Z)
• ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
  We show that a simple iterative mask discovery method can achieve state-of-the-art compression of very deep networks. Our algorithm represents a hybrid approach between single shot network pruning methods and Lottery-Ticket type approaches.
  arXiv  Detail & Related papers  (2020-06-28T23:09:27Z)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  We propose a graph meta-learning framework -- Graph Prototypical Networks (GPN) GPN is able to perform textitmeta-learning on an attributed network and derive a highly generalizable model for handling the target classification task.
  arXiv  Detail & Related papers  (2020-06-23T04:13:23Z)
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure [5.8010446129208155]
  We provide an alternative random graph model with community structure and power-law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD) ABCD is fast, simple, and can be easily tuned to allow the user to make a smooth transition between the two extremes: pure (independent) communities and random graph with no community structure.
  arXiv  Detail & Related papers  (2020-01-14T17:20:27Z)

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.