Hierarchical community structure in networks

• URL: http://arxiv.org/abs/2009.07196v2
• Date: Tue, 25 Apr 2023 08:14:09 GMT
• Title: Hierarchical community structure in networks
• Authors: Michael T. Schaub, Jiaze Li and Leto Peel
• Abstract summary: We present a theoretical study on hierarchical community structure in networks. We address the following questions: 1) How should we define a hierarchy of communities? 2) How do we determine if there is sufficient evidence of a hierarchical structure in a network?
• Score: 1.9981375888949475
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modular and hierarchical community structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions: 1) How should we define a hierarchy of communities? 2) How do we determine if there is sufficient evidence of a hierarchical structure in a network? and 3) How can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

Related papers

• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Inferring community structure in attributed hypergraphs using stochastic block models [3.335932527835653]
  We develop a statistical framework that incorporates node attribute data into the learning of community structure in a hypergraph. We demonstrate that our model, which we refer to as HyperNEO, enhances the learning of community structure in synthetic and empirical hypergraphs. We expect that our framework will broaden the investigation and understanding of higher-order community structure in real-world complex systems.
  arXiv  Detail & Related papers  (2024-01-01T07:31:32Z)
• StructRe: Rewriting for Structured Shape Modeling [63.792684115318906]
  We present StructRe, a structure rewriting system, as a novel approach to structured shape modeling. Given a 3D object represented by points and components, StructRe can rewrite it upward into more concise structures, or downward into more detailed structures.
  arXiv  Detail & Related papers  (2023-11-29T10:35:00Z)
• How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model [47.617093812158366]
  We introduce the Random Hierarchy Model: a family of synthetic tasks inspired by the hierarchical structure of language and images. We find that deep networks learn the task by developing internal representations invariant to exchanging equivalent groups. Our results indicate how deep networks overcome the curse of dimensionality by building invariant representations.
  arXiv  Detail & Related papers  (2023-07-05T09:11:09Z)
• Neural Sculpting: Uncovering hierarchically modular task structure in neural networks through pruning and network analysis [8.080026425139708]
  We show that hierarchically modular neural networks offer benefits such as learning efficiency, generalization, multi-task learning, and transfer. We propose an approach based on iterative unit and edge pruning (during training), combined with network analysis for module detection and hierarchy inference.
  arXiv  Detail & Related papers  (2023-05-28T15:12:32Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs [0.0]
  mesoscale structures are integral part of the abstraction and analysis of complex systems. They can represent communities in social or citation networks, roles in corporate interactions, or core-periphery structures in transportation networks. We derive a Bayesian approach that simultaneously models the optimal partitioning of nodes in groups and the optimal higher-order network dynamics.
  arXiv  Detail & Related papers  (2023-01-16T12:45:33Z)
• Provable Hierarchy-Based Meta-Reinforcement Learning [50.17896588738377]
  We analyze HRL in the meta-RL setting, where learner learns latent hierarchical structure during meta-training for use in a downstream task. We provide "diversity conditions" which, together with a tractable optimism-based algorithm, guarantee sample-efficient recovery of this natural hierarchy. Our bounds incorporate common notions in HRL literature such as temporal and state/action abstractions, suggesting that our setting and analysis capture important features of HRL in practice.
  arXiv  Detail & Related papers  (2021-10-18T17:56:02Z)
• Structure Amplification on Multi-layer Stochastic Block Models [16.53851254884497]
  We propose a general structure amplification technique that uncovers hidden structure in complex networks. HiCODE incrementally weakens dominant structure through randomization allowing the hidden functionality to emerge. We provide theoretical proof that the iterative reducing methods could help promote the uncovering of hidden structure.
  arXiv  Detail & Related papers  (2021-07-31T02:11:47Z)
• 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)

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.