tessl/pypi-igraph

High performance graph data structures and algorithms for Python

—

Pending

Overview

Eval results

Files

Graph Analysis

Name: tessl/pypi-igraph
Author: tessl

Comprehensive analysis algorithms including centrality measures, shortest paths, connectivity analysis, and structural properties. These methods enable deep understanding of network structure and vertex/edge importance.

Capabilities

Centrality Measures

Compute various centrality metrics to identify important vertices in the network.

class Graph:
    def betweenness(self, vertices=None, directed=True, weights=None):
        """
        Calculate betweenness centrality.
        
        Parameters:
        - vertices: list/VertexSeq, vertices to compute (None for all)
        - directed: bool, whether to respect edge directions
        - weights: str/list, edge weights or attribute name
        
        Returns:
        list of float, betweenness centrality values
        """

    def closeness(self, vertices=None, mode=ALL, weights=None, normalized=True):
        """
        Calculate closeness centrality.
        
        Parameters:
        - vertices: vertex selection (None for all)
        - mode: path direction (ALL, IN, OUT)
        - weights: edge weights
        - normalized: bool, whether to normalize by (n-1)
        
        Returns:
        list of float, closeness centrality values
        """

    def eigenvector_centrality(self, directed=True, scale=True, weights=None, return_eigenvalue=False):
        """
        Calculate eigenvector centrality.
        
        Parameters:
        - directed: bool, respect edge directions
        - scale: bool, scale values to unit length
        - weights: edge weights
        - return_eigenvalue: bool, also return dominant eigenvalue
        
        Returns:
        list of float (+ eigenvalue if requested)
        """

    def pagerank(self, vertices=None, directed=True, damping=0.85, weights=None, arpack_options=None):
        """
        Calculate PageRank centrality.
        
        Parameters:
        - vertices: vertex selection (None for all)
        - directed: bool, respect edge directions
        - damping: float, damping parameter (0-1)
        - weights: edge weights
        - arpack_options: ARPACKOptions, solver configuration
        
        Returns:
        list of float, PageRank values
        """

    def authority_score(self, scale=True, weights=None, return_eigenvalue=False):
        """
        Calculate HITS authority scores.
        
        Parameters:
        - scale: bool, scale to unit length
        - weights: edge weights  
        - return_eigenvalue: bool, return eigenvalue
        
        Returns:
        list of float, authority scores
        """

    def hub_score(self, scale=True, weights=None, return_eigenvalue=False):
        """
        Calculate HITS hub scores.
        
        Parameters:
        - scale: bool, scale to unit length
        - weights: edge weights
        - return_eigenvalue: bool, return eigenvalue
        
        Returns:
        list of float, hub scores
        """

Usage Examples:

import igraph as ig

# Create sample network
g = ig.Graph.Famous("Zachary")  # Karate club network

# Betweenness centrality
betw = g.betweenness()
print("Top betweenness:", sorted(enumerate(betw), key=lambda x: x[1], reverse=True)[:3])

# Closeness centrality
close = g.closeness()
print("Top closeness:", sorted(enumerate(close), key=lambda x: x[1], reverse=True)[:3])

# Eigenvector centrality
eigen = g.eigenvector_centrality()
print("Top eigenvector:", sorted(enumerate(eigen), key=lambda x: x[1], reverse=True)[:3])

# PageRank
pr = g.pagerank(damping=0.85)
print("Top PageRank:", sorted(enumerate(pr), key=lambda x: x[1], reverse=True)[:3])

# For directed graphs
g_dir = ig.Graph.Erdos_Renyi(20, 30, directed=True)
auth = g_dir.authority_score()
hubs = g_dir.hub_score()

Shortest Paths

Compute shortest paths and distances between vertices.

class Graph:
    def shortest_paths(self, source=None, target=None, weights=None, mode=OUT):
        """
        Calculate shortest path distances.
        
        Parameters:
        - source: int/list, source vertices (None for all)
        - target: int/list, target vertices (None for all)  
        - weights: str/list, edge weights or attribute name
        - mode: path direction (OUT, IN, ALL)
        
        Returns:
        list/matrix, shortest path distances
        """

    def shortest_paths_dijkstra(self, source=None, target=None, weights=None, mode=OUT):
        """
        Dijkstra's algorithm for shortest paths (non-negative weights).
        
        Parameters:
        - source: source vertices (None for all)
        - target: target vertices (None for all)
        - weights: edge weights (must be non-negative)
        - mode: path direction
        
        Returns:
        Distance matrix
        """

    def get_shortest_paths(self, v, to=None, weights=None, mode=OUT, predecessors=False, inbound_edges=False):
        """
        Get actual shortest paths as vertex sequences.
        
        Parameters:
        - v: int, source vertex
        - to: int/list, target vertices (None for all)
        - weights: edge weights
        - mode: path direction
        - predecessors: bool, return predecessor info
        - inbound_edges: bool, return edge sequences
        
        Returns:
        list of paths (vertex lists)
        """

    def diameter(self, directed=True, unconn=True, weights=None):
        """
        Calculate graph diameter (longest shortest path).
        
        Parameters:
        - directed: bool, respect edge directions
        - unconn: bool, return infinity for unconnected graphs
        - weights: edge weights
        
        Returns:
        float, diameter length
        """

    def average_path_length(self, directed=True, unconn=True):
        """
        Calculate average shortest path length.
        
        Parameters:
        - directed: bool, respect edge directions  
        - unconn: bool, how to handle unconnected pairs
        
        Returns:
        float, average path length
        """

Usage Examples:

# Create weighted graph
g = ig.Graph([(0,1), (1,2), (2,3), (0,3), (1,3)], directed=False)
g.es["weight"] = [1, 2, 1, 4, 1]

# All shortest distances
distances = g.shortest_paths(weights="weight")
print("Distance matrix:", distances)

# Specific source
dist_from_0 = g.shortest_paths(source=[0], weights="weight")[0]
print("Distances from vertex 0:", dist_from_0)

# Get actual paths
paths = g.get_shortest_paths(0, to=[2, 3], weights="weight")
print("Paths from 0 to 2,3:", paths)

# Graph diameter
diam = g.diameter(weights="weight")
print("Diameter:", diam)

# Average path length
avg_path = g.average_path_length()
print("Average path length:", avg_path)

Connectivity Analysis

Analyze graph connectivity and identify components.

class Graph:
    def is_connected(self, mode=WEAK):
        """
        Check if graph is connected.
        
        Parameters:
        - mode: connectivity type (WEAK, STRONG for directed graphs)
        
        Returns:
        bool, True if connected
        """

    def components(self, mode=WEAK):
        """
        Find connected components.
        
        Parameters:
        - mode: component type (WEAK, STRONG)
        
        Returns:
        VertexClustering, component membership
        """

    def articulation_points(self):
        """
        Find articulation points (cut vertices).
        
        Returns:
        list of int, articulation point indices
        """

    def bridges(self):
        """
        Find bridge edges (cut edges).
        
        Returns:
        list of int, bridge edge indices
        """

    def vertex_connectivity(self, source=None, target=None, checks=True):
        """
        Calculate vertex connectivity.
        
        Parameters:
        - source: int, source vertex (None for overall connectivity)
        - target: int, target vertex
        - checks: bool, perform input validation
        
        Returns:
        int, minimum vertex cuts needed to disconnect
        """

    def edge_connectivity(self, source=None, target=None, checks=True):
        """
        Calculate edge connectivity.
        
        Parameters:
        - source: source vertex (None for overall)
        - target: target vertex  
        - checks: bool, input validation
        
        Returns:
        int, minimum edge cuts needed to disconnect
        """

    def st_mincut(self, source, target, capacity=None):
        """
        Calculate minimum s-t cut.
        
        Parameters:
        - source: int, source vertex
        - target: int, target vertex
        - capacity: str/list, edge capacities
        
        Returns:
        Cut object with value, partition, and cut edges
        """

Usage Examples:

# Create graph with components
g1 = ig.Graph([(0,1), (1,2), (3,4), (4,5)])  # Two components

# Check connectivity
print("Connected:", g1.is_connected())  # False

# Find components  
comp = g1.components()
print("Components:", comp.membership)   # [0, 0, 0, 1, 1, 1]
print("Component sizes:", comp.sizes()) # [3, 3]

# Create connected graph for further analysis
g2 = ig.Graph.Ring(8)  # 8-vertex cycle

# Find articulation points and bridges
g2.add_edge(0, 4)  # Add chord
arts = g2.articulation_points()
bridges = g2.bridges()
print("Articulation points:", arts)
print("Bridge edges:", bridges)

# Connectivity measures
v_conn = g2.vertex_connectivity()
e_conn = g2.edge_connectivity()
print(f"Vertex connectivity: {v_conn}")
print(f"Edge connectivity: {e_conn}")

# Minimum cut
cut = g2.st_mincut(0, 4)
print(f"Min cut value: {cut.value}")
print(f"Cut partition: {cut.partition}")

Structural Properties

Analyze various structural characteristics of the graph.

class Graph:
    def transitivity_undirected(self, mode="nan", weights=None):
        """
        Calculate global clustering coefficient.
        
        Parameters:
        - mode: how to handle undefined cases ("nan", "zero")
        - weights: edge weights for weighted transitivity
        
        Returns:
        float, global transitivity
        """

    def transitivity_local_undirected(self, vertices=None, mode="nan", weights=None):
        """
        Calculate local clustering coefficients.
        
        Parameters:
        - vertices: vertex selection (None for all)
        - mode: undefined case handling
        - weights: edge weights
        
        Returns:
        list of float, local clustering coefficients
        """

    def assortativity_degree(self, directed=True, mode1=OUT, mode2=IN):
        """
        Calculate degree assortativity.
        
        Parameters:
        - directed: bool, respect edge directions
        - mode1: source vertex degree type
        - mode2: target vertex degree type
        
        Returns:
        float, degree assortativity coefficient
        """

    def assortativity(self, types1, types2=None, directed=True):
        """
        Calculate attribute assortativity.
        
        Parameters:
        - types1: list, vertex attributes for source vertices
        - types2: list, vertex attributes for target vertices (None = same as types1)
        - directed: bool, respect directions
        
        Returns:
        float, assortativity coefficient
        """

    def reciprocity(self, ignore_loops=True, mode="default"):
        """
        Calculate edge reciprocity.
        
        Parameters:
        - ignore_loops: bool, exclude self-loops
        - mode: reciprocity definition ("default", "ratio")
        
        Returns:
        float, reciprocity measure
        """

    def motifs_randesu(self, size=3, cut_prob=None):
        """
        Count network motifs using RANDESU algorithm.
        
        Parameters:
        - size: int, motif size (3 or 4)
        - cut_prob: list, cutting probabilities for sampling
        
        Returns:
        list of int, motif counts
        """

Usage Examples:

# Create social network-like graph
g = ig.Graph.Barabasi(100, m=3, directed=False)

# Clustering coefficients
global_cc = g.transitivity_undirected()
local_cc = g.transitivity_local_undirected()
print(f"Global clustering: {global_cc:.3f}")
print(f"Average local clustering: {sum(local_cc)/len(local_cc):.3f}")

# Degree assortativity
deg_assort = g.assortativity_degree()
print(f"Degree assortativity: {deg_assort:.3f}")

# Attribute assortativity
import random
g.vs["type"] = [random.choice([0, 1]) for _ in range(g.vcount())]
attr_assort = g.assortativity("type")
print(f"Type assortativity: {attr_assort:.3f}")

# For directed networks
g_dir = ig.Graph.Erdos_Renyi(50, 100, directed=True)
recip = g_dir.reciprocity()
print(f"Reciprocity: {recip:.3f}")

# Motif analysis
motifs = g_dir.motifs_randesu(size=3)
print("Triad counts:", motifs)

Special Graph Measures

Additional structural measures for specific types of analysis.

class Graph:
    def girth(self):
        """
        Calculate graph girth (shortest cycle length).
        
        Returns:
        int, girth (0 if acyclic)
        """

    def radius(self, mode=OUT):
        """
        Calculate graph radius.
        
        Parameters:
        - mode: path direction (OUT, IN, ALL)
        
        Returns:
        float, radius (maximum eccentricity)
        """

    def cohesion(self, checks=True):
        """
        Calculate graph cohesion (vertex connectivity).
        
        Parameters:
        - checks: bool, perform input validation
        
        Returns:
        int, cohesion value
        """

    def adhesion(self, checks=True):
        """
        Calculate graph adhesion (edge connectivity).
        
        Parameters:
        - checks: bool, input validation
        
        Returns:  
        int, adhesion value
        """

    def dyad_census(self):
        """
        Perform dyad census for directed graphs.
        
        Returns:
        DyadCensus object with mutual, asymmetric, null counts
        """

    def triad_census(self):
        """
        Perform triad census for directed graphs.
        
        Returns:
        TriadCensus object with counts for all 16 triad types
        """

Usage Examples:

# Structural measures
g = ig.Graph.Ring(10)
g.add_edges([(0, 5), (2, 7)])  # Add chords

girth = g.girth()
radius = g.radius()
cohesion = g.cohesion()
adhesion = g.adhesion()

print(f"Girth: {girth}")      # Shortest cycle
print(f"Radius: {radius}")    # Maximum eccentricity  
print(f"Cohesion: {cohesion}")   # Vertex connectivity
print(f"Adhesion: {adhesion}")   # Edge connectivity

# For directed graphs
g_dir = ig.Graph.Erdos_Renyi(20, 40, directed=True)

# Dyad census
dyads = g_dir.dyad_census()
print(f"Mutual: {dyads.mutual}, Asymmetric: {dyads.asymmetric}, Null: {dyads.null}")

# Triad census
triads = g_dir.triad_census()
print("Triad type 003 count:", getattr(triads, "003"))  # Empty triad
print("Triad type 300 count:", getattr(triads, "300"))  # Complete triad

Install with Tessl CLI