An official website of the United States government
Abstract Many complex networks in the real world have community structures β groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical/combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By considering networks as geometric objects and communities in a network as a geometric decomposition, we apply curvature and discrete Ricci flow, which have been used to decompose smooth manifolds with astonishing successes in mathematics, to break down communities in networks. We tested our method on networks with ground-truth community structures, and experimentally confirmed the effectiveness of this geometric approach.
more »
« less
Fractal networks: Topology, dimension, and complexity
Over the past two decades, the study of self-similarity and fractality in discrete structures, particularly complex networks, has gained momentum. This surge of interest is fueled by the theoretical developments within the theory of complex networks and the practical demands of real-world applications. Nonetheless, translating the principles of fractal geometry from the domain of general topology, dealing with continuous or infinite objects, to finite structures in a mathematically rigorous way poses a formidable challenge. In this paper, we overview such a theory that allows to identify and analyze fractal networks through the innate methodologies of graph theory and combinatorics. It establishes the direct graph-theoretical analogs of topological (Lebesgue) and fractal (Hausdorff) dimensions in a way that naturally links them to combinatorial parameters that have been studied within the realm of graph theory for decades. This allows to demonstrate that the self-similarity in networks is defined by the patterns of intersection among densely connected network communities. Moreover, the theory bridges discrete and continuous definitions by demonstrating how the combinatorial characterization of Lebesgue dimension via graph representation by its subsets (subgraphs/communities) extends to general topological spaces. Using this framework, we rigorously define fractal networks and connect their properties with established combinatorial concepts, such as graph colorings and descriptive complexity. The theoretical framework surveyed here sets a foundation for applications to real-life networks and future studies of fractal characteristics of complex networks using combinatorial methods and algorithms.
more »
« less
- PAR ID:
- 10543281
- Publisher / Repository:
- AIP Publishing
- Date Published:
- Journal Name:
- Chaos: An Interdisciplinary Journal of Nonlinear Science
- Volume:
- 34
- Issue:
- 4
- ISSN:
- 1054-1500
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Systematic enumeration and identification of unique 3D spatial topologies of complex engineering systems such as automotive cooling layouts, hybrid-electric power trains, and aero-engines are essential to search their exhaustive design spaces to identify spatial topologies that can satisfy challenging system requirements. However, efficient navigation through discrete 3D spatial topology options is a very challenging problem due to its combinatorial nature and can quickly exceed human cognitive abilities at even moderate complexity levels. Here we present a new, efficient, and generic design framework that utilizes mathematical spatial graph theory to represent, enumerate, and identify distinctive 3D topological classes for an abstract engineering system, given its system architecture (SA) β its components and interconnections. Spatial graph diagrams (SGDs) are generated for a given SA from zero to a specified maximum crossing number. Corresponding Yamada polynomials for all the planar SGDs are then generated. SGDs are categorized into topological classes, each of which shares a unique Yamada polynomial. Finally, for each topological class, one 3D geometric model is generated for an SGD with the fewest interconnect crossings. Several case studies are shown to illustrate the different features of our proposed framework. Design guidelines are also provided for practicing engineers to aid the utilization of this framework for application to different types of real-world problems.more » « less
-
Graphs are ubiquitous in various domains, such as social networks and biological systems. Despite the great successes of graph neural networks (GNNs) in modeling and analyzing complex graph data, the inductive bias of locality assumption, which involves exchanging information only within neighboring connected nodes, restricts GNNs in capturing long-range dependencies and global patterns in graphs. Inspired by the classic Brachistochrone problem, we seek how to devise a new inductive bias for cutting-edge graph application and present a general framework through the lens of variational analysis. The backbone of our framework is a two-way mapping between the discrete GNN model and continuous diffusion functional, which allows us to design application-specific objective function in the continuous domain and engineer discrete deep model with mathematical guarantees. First, we address over-smoothing in current GNNs. Specifically, our inference reveals that the existing layer-by-layer models of graph embedding learning are equivalent to a β 2 -norm integral functional of graph gradients, which is the underlying cause of the over-smoothing problem. Similar to edge-preserving filters in image denoising, we introduce the total variation (TV) to promote alignment of the graph diffusion pattern with the global information present in community topologies. On top of this, we devise a new selective mechanism for inductive bias that can be easily integrated into existing GNNs and effectively address the trade-off between model depth and over-smoothing. Second, we devise a novel generative adversarial network (GAN) to predict the spreading flows in the graph through a neural transport equation. To avoid the potential issue of vanishing flows, we tailor the objective function to minimize the transportation within each community while maximizing the inter-community flows. Our new GNN models achieve state-of-the-art (SOTA) performance on graph learning benchmarks such as Cora, Citeseer, and Pubmed.more » « less
-
Abstract Complex biological, neuroscience, geoscience and social networks exhibit heterogeneous self-similar higher order topological structures that are usually characterized as being multifractal in nature. However, describing their topological complexity through a compact mathematical description and deciphering their topological governing rules has remained elusive and prevented a comprehensive understanding of networks. To overcome this challenge, we propose a weighted multifractal graph model capable of capturing the underlying generating rules of complex systems and characterizing their node heterogeneity and pairwise interactions. To infer the generating measure with hidden information, we introduce a variational expectation maximization framework. We demonstrate the robustness of the network generator reconstruction as a function of model properties, especially in noisy and partially observed scenarios. The proposed network generator inference framework is able to reproduce network properties, differentiate varying structures in brain networks and chromosomal interactions, and detect topologically associating domain regions in conformation maps of the human genome.more » « less
-
Systematic enumeration and identification of unique 3D spatial topologies (STs) of complex engineering systems (such as automotive cooling systems, electric power trains, satellites, and aero-engines) are essential to navigation of these expansive design spaces with the goal of identifying new spatial configurations that can satisfy challenging system requirements. However, efficient navigation through discrete 3D ST options is a very challenging problem due to its combinatorial nature and can quickly exceed human cognitive abilities at even moderate complexity levels. This article presents a new, efficient, and scalable design framework that leverages mathematical spatial graph theory to represent, enumerate, and identify distinctive 3D topological classes for a generic 3D engineering system, given its system architecture (SA)βits components and their interconnections. First, spatial graph diagrams (SGDs) are generated for a given SA from zero to a specified maximum number of interconnect crossings. Then, corresponding Yamada polynomials for all the planar SGDs are generated. SGDs are categorized into topological classes, each of which shares a unique Yamada polynomial. Finally, within each topological class, 3D geometric models are generated using the SGDs having different numbers of interconnect crossings. Selected case studies are presented to illustrate the different features of our proposed framework, including an industrial engineering design application: ST enumeration of a 3D automotive fuel cell cooling system (AFCS). Design guidelines are also provided for practicing engineers to aid the application of this framework to different types of real-world problems such as configuration design and spatial packaging optimization.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1063/5.0200632
