Skip to main content

cycle_analysis module, performing minimal cycle basis calculation and the cycle coalescecne algorithm.

Project description

cycle-coalescence-algorithm

Have you ever wondered how cycles in graphs form a vector space and encapsulate nesting information? Here is a tool ready to use, enabling you to calculate the cycle bases, mapping them onto a merging tree, and analyze this tree's asymmetry.

Introduction

This python module allows users to analyze weighted, undirected simple graphs for their nested cycle structure by performing two major functions: Calculating minimal cycle bases (Horton algorithm) and computing the merging tree (cycle coalescence algorithm). The algorithm is described in "Modes et al,'Extracting Hidden Hierarchies in 3D Distribution Networks', 2016" and basically follows the shown scheme below:

  • All fundamentals minimal cyles (minimal number of edges) are listed in the weighted graph G and mapped onto the leaves of a new tree T.
  • Then one identifies the lightest edge e in G and merges the two smallest cycles along this edge, creating a new vertex in the tree T for the merger cycle
  • remove the original two cycles and proceed with the next lightest edge e until all cycles in G are merged
  • finally calculate the tree asymmetry using the techniques of "Van-Pelt et al, 'Tree Asymmetry—A Sensitive and Practical Measure for Binary Topological Trees' ,1992"
  • the asymmetry orderparameter will be be 1 for perfecly asymmetric trees and 0 for perfectly symmetric trees modes Figure taken from: Modes et al,'Extracting Hidden Hierarchies in 3D Distribution Networks', 2016

Installation

pip install cycle_analysis

Usage

Currently this implementation only supports networkx graphs. Call cycle_analysis.cycle_coalescence for graph analysis, while cycle_analysis.test provides you with pre-customized functions to put specific weight patterns onto the graph: random/gradient/nested_square

import networkx as nx
import cycle_analysis.cycle_coalescence as cc
import cycle_analysis.test as cat

# generate a dummy graph for testing
# put an edge weight distribution on the system, available are random/gradient/nested_square
G=nx.grid_graph((7,7,1))
G=cat.generate_pattern(G,'nested_square')

# merge all shortest cycles and calc the merging tree's asymmetry for each branch
asymmetry=cc.calc_cycle_asymmetry(G)
print(asymmetry)

./notebook contains examples to play with in the form of jupyter notebooks

Requirements

python3.6+,networkx, numpy

Gallery

random weight distribution
random

nested square weight distribution
nested

gradient weight distribution
gradient

Acknowledgement

cycle_analysis written by Felix Kramer

This implementation is based on the cycle coalescence algorithm as described by Modes et al, 2016. Please acknowledge if used for any further publication or projects.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

cycle_analysis-0.0.4.tar.gz (8.2 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page