/math_cics

A list of mathematical concepts and applications for the study of Complex Interconnected Systems

Mathematics for Complex Interconnected Systems

This is a list of mathematical concepts that have been applied to the study of Complex Interconnected Systems (CICS). Here, by CICS we mean systems that have been modeled in the literature as either networks (directed, weighted, multi-layered, hyperedges, etc) or, more recently, as simplicial complexes.

The purpose is to gather in one place a list of mathematical objects and techniques that authors have used to study CICS. Usually, presentations of the mathematical techniques involved in CICS is either delimited to graph theory, or some technique is presented isolated of all others. Here, we try to categorize these mathematical objects by the branch of mathematics they stem from, as well as what is the primary use of each object.

The following list is broken down into sections, one for each broad mathematical field. Note that many of the concepts in the list could be categorized under two or more sections. Each item is further labeled with one of the following labels:

  • rep: representation. Mathematical objects that can be used to represent CICS. For example, a graph is an obj that represents a CICS.
  • msr: measure. A concept or algorithm that summarizes a CICS into a single number. For example, average degree is a msr that summarizes a CICS to a real number.
  • app: application. A method or technique applying some concepts in order to study CICS. For example, spectral clustering is an app that uses the Laplacian matrix (rep) of a graph (rep) in order to find communities.
  • rel: relation. An object whose purpose is to establish a relationship or equivalence between two other objects. For example, graph isomorphism is a rel that leaves average degree (msr) invariant.
  • obj: object: other mathematical concepts that do not fit in the categories above.

This categorization is completely arbitrary and the authors of the list do not claim that it is complete or rigorously correct beyond intuition. This categorization is made due to the fact that there are commonalities in the study of mathematical objects according to the label attached to an object. That is, given an object, we can ask the following questions according to its label.

  • rep

    • How much information does this rep contain and how does it compare to other reps of the same CICS?

  • msr

    • What is the range of this msr?
    • How efficiently can we compute or approximate this msr?
    • Does this msr discriminate well between different types of CICS?
    • Is there a rel that leaves this msr invariant?

  • app

    • What is the computational pipeline we need to implement in order to use this app?
    • Why is this a good way of studying a CICS? What does this app tell us about the CICS?

  • rel

    • Which properties of CICS are fixed by this rel? That is which msrs are invariant under this rel?
    • How difficult is it to determine that two CICS are equivalent using this rel?

Note: some of the concepts used here to organize the list (e.g. invariant and relation) can be interpreted in terms of symmetry. For a study of symmetry in network science, see ref.

The List

Graph Theory

Colorings and homomorphisms rel

  1. Definition of homomorphism. ref

  2. Constraint satisfaction problems can be encoded as graph homomorphism problems. ref

  3. Subgraph frequencies can be counted using homomorphism theory. ref

  4. Manuscript with a short review on results from homomorhpism theory. ref

Isomorphisms rel

  1. Deciding if two graphs are isomorphic is NP but unknown if it's NP-complete. ref

Graphic matroid obj

  1. The graphic matroid is a matroid whose independent sets are the forests in a given undirected graph. ref

Centrality msr

  1. Centrality is an indicator of how important an element of CICS is. ref

  2. Many different centrality measures can be studied under the same unifying framework. ref

Algebra

Matrices: adjacency rep and Laplace obj rep

  1. These matrices define linear transformations over the set of node-functions.

  2. One can also multiply these matrices by an arbitrary linear transformation. Thus, if the adjacency matrices of two graphs are related by a linear operator $L$, we can say that $L$ defines a rel between them. Eigenvalues are msrs held constant by these linear rels.

Spectral Clustering app

  1. Spectral Clustering is an algorithm that uses the Laplacian Matrix rep of a graph to find communities (or 'clusters'). ref

The trace monoid of graph walks obj

  1. 'Walks on graph obey a semi-commutative extension of number-theory. This insights raises the possibility of using number-htoeretic sieves to count combinatorial objects in graph theory. In particular, the problems of counting cycle double covers and simple cycles/paths on a graph are both amenable to semi-commutative generalisation of the Selberg sieve. My current research aims at exploiting this observation to obtain a tractable bound on the asymptotic growth of the number of simple cycles on regular lattices.' ref

An Hopf algebra for finding simple cycles obj

  1. ref

Cycle Space obj

  1. The set of eulerian subgraphs generates a vector space. ref

Graphs of groups obj

  1. ref

Topology

Homeomorphism rel

  1. Leaves invariant all topological msrs. The operations of sub-divisions and smoothening create homeomorphic graphs. ref

Covering Space obj

  1. Used in algebraic topology to simplify the study of certain topological spaces. ref

Topological Data Analysis app

  1. ref

Embeddings app

  1. Traditionally, mathematicians tried to draw graphs over the plane or other surfaces. ref

  2. However, now some authors relax the conditions and try to find approximate embeddings (or 'drawings'). ref1 ref2 ref3

Simplicial complexes rep

  1. A higher-dimensional way to represent interactions in a CICS. ref

Homotopy and the Fundamental Group obj

  1. Homotopy-equivalence is a rel that is less strict than homeomorphism. [citation needed]

  2. Homotopy groups contain more information than homology groups. ref

  3. Embeddings vs Homotopy: in embeddings, one tries to place the network/CICS as neatly as possible onto a surface or other space. With homotopy, one tries to place other spaces (say, a circumference) as neatly as possible on the graph.

  4. Graph Homotopy: ref

Labeling Schemes app(?)

  1. A labeling scheme on a topological space is an assignment of a label to each of its elements. The purpose is to quotient the space by identifying the elements with the same label. For example, one can label the sides of a polygon, to then identify them and construct the quotient space ref.

  2. Labeling schemes can be used to study the fundamental group of the quotient space ref.

  3. Can labeling schemes tell us anything about graph homotopy? Read ref ch. 80, sec. "cutting and pasting".

  4. An example application using "cutting and pasting", covering spaces, and other topological concepts, see ref.

Homology obj app

  1. "Two's company, three is a simplex" ref

  2. "Homological algebra and data" ref

  3. "Local homology and stratification" ref

  4. A Course on "Toplogy and its Applications" ref

Persistent Homology app(?)

  1. [citation needed]

Geometry

Networks of Manifolds obj rep(?)

  1. ref

Curvature msr

  1. ref

  2. ref

volume entropy msr

  1. ref

Cone over a graph obj

  1. ref

Other references

  1. Thirty essays in Geometrig Graph Theory

Game Theory

  1. Evolutionary Dynamics ref

  2. Games on Graphs ref

  3. Evolutionary Games on Graphs ref

Analysis

Graph convergence app(?)

  1. ref1 ref2

Graphons obj rep(?)

  1. They are the limiting object of a sequence of dense graphs. ref

Modulus msr obj

  1. Provides a generalization of several standard graph-theoretical msrs that deal with distance. ref

Probability

Wasserstein Space obj rep(?)

  1. The space of probability measures over (a.k.a. the Wasserstein Space of) a metric space characterizes the space [citation needed]. We can then convert the graph/CICS into a metric space and study its Wasserstein space.

  2. The eigenvalues of the adjacency matrix of a random undirected graph are distributed as a semi-circle in the limit of large number of nodes. ref