Sequential locality of graphs and its hypothesis testing
arXiv:2111.11267 · doi:10.1103/PhysRevResearch.5.023007
Abstract
The adjacency matrix is the most fundamental and intuitive object in graph analysis that is useful not only mathematically but also for visualizing the structures of graphs. Because the appearance of an adjacency matrix is critically affected by the ordering of rows and columns, or vertex ordering, statistical assessment of graphs together with their vertex sequences is important in identifying the characteristic structures of graphs. In this paper, we propose a hypothesis testing framework that assesses how locally vertices are connected to each other along a specified vertex sequence, which provides a statistical foundation for an optimization problem called envelope reduction or minimum linear arrangement. The proposed tests are particularly suitable for moderately small data and formulated based on a combinatorial approach and a block model with intrinsic vertex ordering.
arXiv comment23 pages, 11 figures
References in corpus (12)
- Community structure in social and biological networks
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Random Walks on Multiplex Networks
- The ground truth about metadata and community detection in networks
- Assessing the relevance of node features for network structure
- Clique Graphs and Overlapping Communities
- Entropy of stochastic blockmodel ensembles
- A goodness-of-fit test for stochastic block models
- A simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks
- Finite size analysis of the detectability limit of the stochastic block model
- Clustering matrices through optimal permutations