Package `aisa`

Auto-Information State Aggregation

This is a python module aimed at partitioning networks through the maximization of Auto-Information. If you use this code, please cite the following paper:

State aggregations in Markov chains and block models of networks,
Faccin, Schaub and Delvenne, Phys. Rev. Lett., 127(7) p.078301 (2021)
ArXiv 2005.00337

(data used in the paper to analyse the ocean surface currents can be found in the Github repo ocean_surface_dataset)

The module provides also a function to compute the Entrogram of a network with a suitable partition. The Entrogram provides a concise, visual characterization of the Markovianity of the dynamics projected to the partition space. In case you use this, please cite the following paper:

Entrograms and coarse graining of dynamics on complex networks,
Faccin, Schaub and Delvenne, Journal of Complex Networks, 6(5) p. 661-678 (2018),
ArXiv 1711.01987

Getting the code

Requirements

The following modules are required to aisa to work properly:

numpy and scipy
networkx
tqdm (optional)

Install

Pip

AISA can be installed directly from PyPI using pip with the following:

pip install aisa

Manually

Alternatively one can download the code here and unzip locally or clone the git repository from Github. From inside the module folder you can run:

pip install aisa

Uninstall

On the terminl run:

$ pip uninstall aisa

Usage

Read the online documentation that describes all classes and functions of the module.

Some simple notebook examples on module usage are provided in the examples subfolder:

a simple example of computing and drawing the entrogram() and detecting the partition that maximize the auto-information in a well know small social network, see in nbviewer
an example on how to build a range dependent network and find the partition that maximize auto-nformation, see in nbviewer

License

AISA is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

AISA is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Check LICENSE.txt for details.

Sub-modules

aisa.base
aisa.utils: Utility functions and classes.

Functions

def best_partition(graph, T=None, beta=0.0, init_part=None, kmin=None, kmax=None, invtemp=1000000.0, compute_steady=True, tsteps=10000)

Find the best partition for graph.

Parameters

graph : nx.Graph or nx.DiGraph: The graph to be aggregated (a random walk is considered as dynamical system)
init_part : dict, optional: initial partition to start the optimization. (Default: N singletons)
T : int, default=None: time scale parameter value. Default to None, meaning it will in fact use T=1
beta : float, default=0.0: model selection parameter.
kmin : int: minimum number of partition to be accepted
kmax : int: maximum number of partition to be accepted
invtemp : float, default=1e6: the inverse of the pseudo-temperature for the simulated annealing process
compute_steady : bool: If steady state need to be computed. (Default: True) If False, the steady state will be the marginal.
tsteps : int: Maximum number of steps in the optimization process. (Default: 10k)

Returns

partition : dict: Dictionary with nodes as keys and partitions as values.
autoinformation : float: Value of the autoinformation

Raises

ValueError :: init_part should be None or dict

def entrogram(graph, partition, depth=3)

Compute the entrogram for the graph and the given partition.

A random walk is assumed as Markovian process on the original network.

Parameters

graph : nx.Graph or nx.DiGraph
partition : dict: A dictionary with nodes as keys and values as classes.
depth : int: The number of bars the final entrogram should have. (Default: 3)

Returns

entrogram : tuple

( H_{KS} )
list of entrogram entries

def merge_pgraph(pgraph, beta=0.0, kmin=1, kmax=inf)

Hierarchical merging of classes.

pgraph will be updated to the best encounteded partition.

Parameters

pgraph : PGraph: A graph plus partition.
beta : float: Model selection parameter (Default: 0.0)
kmin : int: minimum number of partition to be accepted
kmax : int: maximum number of partition to be accepted

def optimize(pgraph, kmin, kmax, invtemp, tsteps, beta=0.0)

Optimize the partition enbedded into pgraph.

Parameters

pgraph : PGraph: A graph plus partition.
kmin : int: minimum number of partition to be accepted
kmax : int: maximum number of partition to be accepted
invtemp : float: the inverse of the pseudo-temperature for the simulated annealing process
tsteps : int: Maximum number of steps in the optimization process. (Default: 10k)

Returns

best_partition : dict: best partition after otpimization (pgraph will be updated accordingly)

Classes

class PGraph (graph, init_part=None, compute_steady=True, T=None)

A graph with a partition.

Initialize from networkx graphs.

Parameters

graph : nx.[Di]Graph(): The graph
init_part : dict: initial partition to start the optimization. (Default: N singletons)
compute_steady : bool: If steady state need to be computed. (Default: True) If False, the steady state will be the marginal.
T : int: time scale parameter value. (Default: 1)

Instance variables

var nn: Return the number of nodes.
var np: Return the number of partitions.

Methods

def autoinformation(self, beta)

Return the autoinformation value for the current partion.

Parameters

beta : float: model selection parameter. (Default: 0)

Returns

autoinformation : float: the autoinformation

def merge_partitions(self, part1, part2)

Merge partitions into one.

Merge partition part1 and part2 and update pgraph accordingly.

Parameters

part1 : int: integer index of the first partition to be merged
part2 : int: integer index of the second partition to be merged

def nodes(self)

Iterate over nodes names.

Yields

nodes

def partition(self)

Return the partition.

Returns

partition : dict: a dictionary with nodes as keys and classes as values.

def print_partition(self)

Try to print the partition to screen using ASCII chars.

def set_partition(self, partition=None)

Set/Change the graph partition.

Parameters

partition : dict: The partition to be set. A dict with nodes as keys and classes as values