Statistical tests for the sequential locality of graphs

You can assess the statistical significance of the sequential locality of an adjacency matrix (graph + vertex sequence) using sequential_locality.py.

This file also includes ORGM.py that generates an instance of the ordered random graph model (ORGM) [1] and spectral.py that yields an optimized vertex sequence based on the spectral ordering algorithms.

Please find Ref. [1] for the details of the statistical tests.

sequential_locality.py

sequential_locality.py executes statistical tests with respect to the sequential locality.

Simple example

import numpy as np
import igraph
import sequential_locality as seq

s = seq.SequentialLocality(
		g = igraph.Graph.Erdos_Renyi(n=20,m=80), 
		sequence = np.arange(20)
		)
s.H1()

{'H1': 1.0375,
 'z1': 0.5123475382979811,
 'H1 p-value (ER/ORGM)': 0.6957960998835012,
 'H1 p-value (random)': 0.7438939644617626,
 'bandwidth_opt': None}

Please find Demo.ipynb for more examples.

SequentialLocality

This is a class to be instantiated to assess the sequential locality.

Input parameters

Either g or edgelist must be provided as an input.

H1

This is a method that returns H₁ and z₁ test statistics and p-values of the input data.

Input parameters

Output parameters

HG

This is a method that returns H_G and z_G test statistics and p-values of the input data.

• There is no in_envelope option for the test based on H_G.
• random_sequence = 'analytical' can be computationally demanding.

Input parameters

Output parameters

ORGM.py

ORGM.py is a random graph generator. It generates an ORGM [1] instance that has a desired strength of sequentially lcoal structure.

Simple example

import ORGM as orgm

edgelist, valid = orgm.ORGM(
	N=20, M=80, bandwidth=10, epsilon=0.25
	)

Input parameters

spectral.py

spectral.py is an implementation of the spectral ordering [2].

Simple example

import graph_tool.all as gt
import spectral

g_real = gt.collection.ns['karate/77']
inferred_sequence = spectral.spectral_sequence(
	g= g_real, 
	format='graph-tool'
	)

Citation

Please use Ref. [1] for the citation of the present code.

References

• [1] Tatsuro Kawamoto and Teruyoshi Kobayashi, "Sequential locality of graphs and its hypothesis testing," arXiv:2111.11267 (2021).
• [2] Chris Ding and Xiaofeng He, "Linearized Cluster Assignment via Spectral Ordering," Proceedings of the Twenty-First International Conference on Machine Learning (ICML) (2004).