0100482176

open access

Version of Record

Sequential locality of graphs and its hypothesis testing

English (英語)

Physical Review Research

5(2)

023007

American Physical Society (APS)

2023-04

2023-06-14

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 sets and formulated based on a combinatorial approach and a block model with intrinsic vertex ordering.

学術雑誌論文

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.