Geodesic statistics for random network families

• URL: http://arxiv.org/abs/2111.02330v1
• Date: Wed, 3 Nov 2021 16:25:39 GMT
• Title: Geodesic statistics for random network families
• Authors: Sahil Loomba, Nick S. Jones
• Abstract summary: We derive measures of node and network connectivity that can contribute to explain such phenomena. We provide specific results for widely used network families like block models, dot-product graphs, random graphs, and graphons. Notably, the shortest path length distribution allows us to derive, for the network families above, important graph properties like the bond percolation threshold, size of the giant component, average shortest path length, and closeness and betweenness centralities.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A key task in the study of networked systems is to derive local and global properties that impact connectivity, synchronizability, and robustness. Computing shortest paths or geodesics in the network yields measures of node centrality and network connectivity that can contribute to explain such phenomena. We derive an analytic distribution of shortest path lengths, on the giant component in the supercritical regime or on small components in the subcritical regime, of any sparse (possibly directed) graph with conditionally independent edges, in the infinite-size limit. We provide specific results for widely used network families like stochastic block models, dot-product graphs, random geometric graphs, and graphons. The survival function of the shortest path length distribution possesses a simple closed-form lower bound which is asymptotically tight for finite lengths, has a natural interpretation of traversing independent geodesics in the network, and delivers novel insight in the above network families. Notably, the shortest path length distribution allows us to derive, for the network families above, important graph properties like the bond percolation threshold, size of the giant component, average shortest path length, and closeness and betweenness centralities. We also provide a corroborative analysis of a set of 20 empirical networks. This unifying framework demonstrates how geodesic statistics for a rich family of random graphs can be computed cheaply without having access to true or simulated networks, especially when they are sparse but prohibitively large.

Related papers

• DANI: Fast Diffusion Aware Network Inference with Preserving Topological Structure Property [2.8948274245812327]
  We propose a novel method called DANI to infer the underlying network while preserving its structural properties. DANI has higher accuracy and lower run time while maintaining structural properties, including modular structure, degree distribution, connected components, density, and clustering coefficients.
  arXiv  Detail & Related papers  (2023-10-02T23:23:00Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  Heterogeneous graph neural networks (HGNNs) have powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) over homogeneous graphs, especially the attention mechanism and the multi-layer structure. This paper conducts an in-depth and detailed study of these mechanisms and proposes Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN)
  arXiv  Detail & Related papers  (2022-07-06T10:01:46Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• 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)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
  We perform a massive evaluation of neural networks with architectures corresponding to random graphs of various types. We find that none of the classical numerical graph invariants by itself allows to single out the best networks. We also find that networks with primarily short-range connections perform better than networks which allow for many long-range connections.
  arXiv  Detail & Related papers  (2020-02-19T11:04:49Z)
• Latent Poisson models for networks with heterogeneous density [0.0]
  Empirical networks are often globally sparse, with a small average number of connections per node, when compared to the total size of the network. We show how latent Poisson models which generate hidden multigraphs can be effective at capturing this density, while being more tractable mathematically than some of the alternatives that model simple graphs directly.
  arXiv  Detail & Related papers  (2020-02-18T18:58:13Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.