Statistical tests for the sequential locality of graphs

Overview

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.

Parameter Value Default Description
g graph None Graph (undirected, unweighted, no self-loops) in igraph or graph-tool.
edgelist list of tuples None Edgelist as a list of tuples.
sequence 1-dim array None Array (list or ndarray) indicating the vertex ordering. If provided, the vertex indices in the graph will be replaced based on sequence . If sequence is None, the intrinsic vertex indices in the graph or edgelist will be used as the sequence .
format 'igraph' or 'graph-tool' 'igraph' Input graph format
simple Boolean True If True, the graph is assumed to be a simple graph, otherwise the graph is assumed to be a multigraph.

H1

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

Input parameters

Parameter Value Default Description
random_sequence 'analytical' or 'empirical' 'analytical' If 'analytical' is selected, the p-value based on the normal approximation will be returned for the test of vertex sequence H1 p-value (random). If 'empirical' is selected, the p-value based on random sequences specified by samples will be returned.
n_samples Integer 10,000 Number of samples to be drawn as a set of random sequences. This is used only when random_sequence = 'empirical'.
in_envelope Boolean False If False, the p-value based on the ER model will be returned. If True, the p-value based on the ORGM will be returned. That is, the matrix elements outside of the bandwidth r will be ignored.
r Integer None An integer between 1 and N-1. If provided, r will be used as the bandwidth when in_envelope=True.

Output parameters

Parameter Description
H1 H1 test statistic of the input data (graph & vertex sequence)
z1 z1 test statistic of the input data
H1 p-value (ER/ORGM) p-value under the null hypothesis of the ER random graph (when in_envelope=False) or the ORGM (when in_envelope=True).
H1 p-value (random) p-value under the null hypothesis of random sequences
bandwidth_opt Maximum likelihood estimate (MLE) of the bandwidth (when r=None in the input) or the input bandwidth r

HG

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

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

Input parameters

Parameter Value Default Description
random_sequence 'analytical' or 'empirical' 'empirical' If 'analytical' is selected, the p-value based on the normal approximation will be returned for the test of vertex sequence H1 p-value (random). If 'empirical' is selected, the p-value based on random sequences specified by samples will be returned.
n_samples Integer 10,000 Number of samples to be drawn as a set of random sequences. This is used only when random_sequence = 'empirical'.

Output parameters

Parameter Description
HG HG test statistic of the input data (graph & vertex sequence)
zG zG test statistic of the input data
HG p-value (ER) p-value under the null hypothesis of the ER random graph.
HG p-value (random) p-value under the null hypothesis of random sequences

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

Parameter Value Default Description
N Integer required input Number of vertices
M Integer required input Number of edges
bandwidth Integer required input Bandwidth of the ORGM
epsilon Float (in [0,1]) required input Density ratio between the adjacency matrix elements inside & outside of the envelope. When epsilon=1, the ORGM becomes a uniform model. When epsilon=0, the nonzero matrix elements are strictly confined in the envelope.
simple Boolean True If True, the graph is constrained to be simple. If False, the graph is allowed to have multiedges.

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'
	)
Parameter Value Default Description
g graph required input graph (undirected, unweighted, no self-loops) in igraph or graph-tool
normalized Boolean True Normalized Laplacian (True) vs unnormalized (combinatorial) Laplacian (False)
format 'igraph' or 'graph-tool' 'igraph' Input graph format

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).
A automated browsing experience.

browser-automation This app is an automated browsing technique where one has to enter the required information, it's just like searching for Animals o

Ojas Barawal 3 Aug 04, 2021
Cornell record & replay mock server

Cornell: record & replay mock server Cornell makes it dead simple, via its record and replay features to perform end-to-end testing in a fast and isol

HiredScoreLabs 134 Sep 15, 2022
User-oriented Web UI browser tests in Python

Selene - User-oriented Web UI browser tests in Python (Selenide port) Main features: User-oriented API for Selenium Webdriver (code like speak common

Iakiv Kramarenko 575 Jan 02, 2023
Sixpack is a language-agnostic a/b-testing framework

Sixpack Sixpack is a framework to enable A/B testing across multiple programming languages. It does this by exposing a simple API for client libraries

1.7k Dec 24, 2022
Repository for JIDA SNP Browser Web Application: Local Deployment

JIDA JIDA is a web application that retrieves SNP information for a genomic region of interest in Homo sapiens and calculates specific summary statist

3 Mar 03, 2022
Spam the buzzer and upgrade automatically - Selenium

CookieClicker Usage: Let's check your chrome navigator version : Consequently, you have to : download the right chromedriver in the follow link : http

Iliam Amara 1 Nov 22, 2021
pytest plugin for a better developer experience when working with the PyTorch test suite

pytest-pytorch What is it? pytest-pytorch is a lightweight pytest-plugin that enhances the developer experience when working with the PyTorch test sui

Quansight 39 Nov 18, 2022
API Test Automation with Requests and Pytest

api-testing-requests-pytest Install Make sure you have Python 3 installed on your machine. Then: 1.Install pipenv sudo apt-get install pipenv 2.Go to

Sulaiman Haque 2 Nov 21, 2021
Show surprise when tests are passing

pytest-pikachu pytest-pikachu prints ascii art of Surprised Pikachu when all tests pass. Installation $ pip install pytest-pikachu Usage Pass the --p

Charlie Hornsby 13 Apr 15, 2022
Voip Open Linear Testing Suite

VOLTS Voip Open Linear Tester Suite Functional tests for VoIP systems based on voip_patrol and docker 10'000 ft. view System is designed to run simple

Igor Olhovskiy 17 Dec 30, 2022
Pytest modified env

Pytest plugin to fail a test if it leaves modified os.environ afterwards.

wemake.services 7 Sep 11, 2022
Penetration testing

Penetration testing

3 Jan 11, 2022
d4rk Ghost is all in one hacking framework For red team Pentesting

d4rk ghost is all in one Hacking framework For red team Pentesting it contains all modules , information_gathering exploitation + vulnerability scanning + ddos attacks with 12 methods + proxy scraper

d4rk sh4d0w 15 Dec 15, 2022
Free cleverbot without headless browser

Cleverbot Scraper Simple free cleverbot library that doesn't require running a heavy ram wasting headless web browser to actually chat with the bot, a

Matheus Fillipe 3 Sep 25, 2022
Front End Test Automation with Pytest Framework

Front End Test Automation Framework with Pytest Installation and running instructions: 1. To install the framework on your local machine: clone the re

Sergey Kolokolov 2 Jun 17, 2022
Testinfra test your infrastructures

Testinfra test your infrastructure Latest documentation: https://testinfra.readthedocs.io/en/latest About With Testinfra you can write unit tests in P

pytest-dev 2.1k Jan 07, 2023
Pyramid debug toolbar

pyramid_debugtoolbar pyramid_debugtoolbar provides a debug toolbar useful while you're developing your Pyramid application. Note that pyramid_debugtoo

Pylons Project 95 Sep 17, 2022
A friendly wrapper for modern SQLAlchemy and Alembic

A friendly wrapper for modern SQLAlchemy (v1.4 or later) and Alembic. Documentation: https://jpsca.github.io/sqla-wrapper/ Includes: A SQLAlchemy wrap

Juan-Pablo Scaletti 129 Nov 28, 2022
ApiPy was created for api testing with Python pytest framework which has also requests, assertpy and pytest-html-reporter libraries.

ApiPy was created for api testing with Python pytest framework which has also requests, assertpy and pytest-html-reporter libraries. With this f

Mustafa 1 Jul 11, 2022
Python package to easily work with selenium and manage tabs effectively.

Simple Selenium The aim of this package is to quickly get started with working with selenium for simple browser automation tasks. Installation Install

Vishal Kumar Mishra 1 Oct 27, 2021