On the use of local structural properties for improving the efficiency of hierarchical community detection methods

• URL: http://arxiv.org/abs/2009.06798v1
• Date: Tue, 15 Sep 2020 00:16:12 GMT
• Title: On the use of local structural properties for improving the efficiency of hierarchical community detection methods
• Authors: Julio-Omar Palacio-Ni\~no and Fernando Berzal
• Abstract summary: 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.
• Score: 77.34726150561087
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community detection is a fundamental problem in the analysis of complex networks. It is the analogue of clustering in network data mining. Within community detection methods, hierarchical algorithms are popular. However, their iterative nature and the need to recompute the structural properties used to split the network (i.e. edge betweenness in Girvan and Newman's algorithm), make them unsuitable for large network data sets. In this paper, we study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection while, at the same time, achieving competitive results in terms of modularity. In particular, we study the potential use of the structural properties commonly used to perform local link prediction, a supervised learning problem where community structure is relevant, as nodes are prone to establish new links with other nodes within their communities. In addition, we check the performance impact of network pruning heuristics as an ancillary tactic to make hierarchical community detection more efficient

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)
• Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis [2.615648035076649]
  We propose a novel deep graph clustering framework with temporal consistency regularization on inter-community structures. MFC is a matrix factorization-based deep graph clustering algorithm that preserves node embedding. TopoReg is introduced to ensure the preservation of topological similarity between inter-community structures over time intervals.
  arXiv  Detail & Related papers  (2024-01-06T11:29: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)
• The Influence of Network Structural Preference on Node Classification and Link Prediction [0.0]
  This work introduces a new feature abstraction method, namely the Transition Probabilities Matrix (TPM) The success of the proposed embedding method is tested on node identification/classification and link prediction on three commonly used real-world networks.
  arXiv  Detail & Related papers  (2022-08-07T12:56:28Z)
• Network Clustering for Latent State and Changepoint Detection [0.0]
  We propose a convex approach for the task of network clustering. We provide an efficient algorithm for convex network clustering and demonstrate its effectiveness on synthetic examples.
  arXiv  Detail & Related papers  (2021-11-01T21:51:45Z)
• 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)
• Learning Structures for Deep Neural Networks [99.8331363309895]
  We propose to adopt the efficient coding principle, rooted in information theory and developed in computational neuroscience. We show that sparse coding can effectively maximize the entropy of the output signals. Our experiments on a public image classification dataset demonstrate that using the structure learned from scratch by our proposed algorithm, one can achieve a classification accuracy comparable to the best expert-designed structure.
  arXiv  Detail & Related papers  (2021-05-27T12:27:24Z)
• 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)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• 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)

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.