hypergraph-markov-memory

name	hypergraph-markov-memory
description	Tensor-based framework for higher-order Markov chains with memory on hypergraphs. Use when modeling complex systems with group interactions, memory effects, non-pairwise connections, or analyzing higher-order networks. Keywords: hypergraph, Markov chains, memory, tensor, higher-order networks, complex systems, random walks.

Markov Chains with Memory on Hypergraphs

Unified tensor framework for modeling higher-order Markov chains with memory effects in complex systems with group structure.

Problem: Beyond Pairwise Interactions

Many complex systems have:

• Group structure: Interactions involve >2 nodes (hyperedges)
• Memory effects: Current state depends on history
• Higher-order dynamics: Not captured by pairwise networks

Solution: Tensor Framework

Even-Order Paired Tensor

Links folded (aggregated) and unfolded (detailed) dynamics:

• Folded: Aggregate state representation
• Unfolded: Detailed transition structure

Tensor formulation:

• Characterizes steady states
• Proves convergence properties
• Enables analysis of memory-dependent dynamics

Key Innovation

Markov chain with memory ≈ Low-dimensional nonlinear tensor system

This approximation:

• Enables full system analysis
• Preserves essential dynamics
• Reduces computational complexity

Hypergraph Random Walks

Memory naturally arises from hyperedge structure:

• Walker on hyperedge → multiple node options
• Previous hyperedge influences next choice
• Memory encoded in transition tensor

Mathematical Framework

Transition Tensor

$P_{i,j,k,...}$: Transition probability from state $(i,j)$ to $k$

Higher-order tensor captures:

• Current position
• Memory (past positions)
• Next position

Steady State Analysis

Tensor eigenvalue problem:

• Nonlinear system for steady state
• Convergence guaranteed under conditions

Design Applications

1. Social Network Analysis

Groups (hyperedges) influence behavior:

• Memory: Past group membership affects future
• Higher-order: Group dynamics, not just pairs

2. Biological Networks

Protein complexes (hyperedges):

• Memory: Previous complex membership
• Dynamics: Complex formation/ dissolution

3. Transportation

Routes (hyperedges = multiple stops):

• Memory: Route history affects choices
• Analysis: Traffic flow patterns

Implementation Concept

# Traditional: pairwise transition matrix
P[i,j]  # Probability i → j

# Hypergraph with memory: higher-order tensor
P[i,j,k]  # Probability (i,j) → k (memory included)

# Folded representation (aggregated)
P_folded[m, n]  # From memory state m to n

# Unfolded representation (detailed)
P_unfolded[i,j,k]  # Full detail

Key Properties

1. Convergence: Under appropriate conditions, system converges to steady state
2. Memory Integration: Past states naturally influence transitions
3. Group Dynamics: Hyperedges capture multi-node interactions

When to Use

• Complex systems beyond pairwise interactions
• Systems with memory/history effects
• Networks with group structure
• Higher-order topological analysis

Related Concepts

• Hypergraphs: Sets of nodes (hyperedges) vs. pairs (edges)
• Higher-order networks: Beyond pairwise interactions
• Simplicial complexes: Topological structure
• Tensor networks: High-dimensional data structures

References

• arXiv:2604.06895v1 - "Markov Chains and Random Walks with Memory on Hypergraphs: A Tensor-Based Approach"
• Carletti et al. (2020) - Random walks on hypergraphs
• Battiston et al. (2020) - Networks beyond pairwise interactions