mcbosch

Specnet

This project is aimed to build a workable python package to work with general graphs including magnetic graphs, analysisi on graphs (in a sense of functional analysis), and with spectral graph theory.

In this documentation we'll go through the mathematics theory and the package usage. For the repository structure go here and for an updated version of the code explanations we encourage to read the docstring in the sourcecode.

Mathematic Definitions

To work with magnetic graphs we first introduce the discrete (finite) graphs. A discrete graph is a tuple \(G = (V,E)\), where \(V=V(G)\) is the set of nodes and \(E = E(G)\) is the set of edges. The set of edges \(E\) defines relations on the nodes. In these graphs we allow having multiple edges and loops. Thus, instead of writing the edges as tuples \((u,v)\) we use letter \(e\) and distinguish source and pointing nodes with the boundary functions.

The boundary functions are two functions \(\partial_-\) and \(\partial_+\) that indicate the source and the pointing node respectively. These functions form the boundary map \(\partial:E\rightarrow V\times V\), where \(\partial e = (\partial_-e,\partial_+e)\). The graphs can have weights, that is \(w: V\rightarrow [0,\infty)\) and \(w: E\rightarrow [0,\infty)\). If these functions are different than mapping every node/edge to \(1\) (combinatorial weight), we say that we have a weighted graph \(G = (V,E,w)\).

A disctete magnetic graph is a discrete graph with a magnetic potential defined over the edges \(\alpha:E\rightarrow\mathbb{T} = \mathbb{R}/2\pi\mathbb{Z}\). Here we denote it as \(\mathbf{G}=(G,\alpha)\); note that \(G\) can be weighted. We are going to distinguish between two kinds of magnetic graphs; the symmetric ones and the non symmetric. We say that a magnetic graph is symmetric, if there exists an inversion map \(\overline{(\cdot)}:E\rightarrow E\) fullfilling \(\overline{e}\ne e\), \(\overline{\overline{e}}=e\), \(\partial_+\overline{e} = \partial_-e\), and with the restrictions \(w(\overline{e})=w(e)\) and \(\alpha(\overline{e}) = -\alpha(e)\). With this knowledge we can define the adjacent edges of a node \(v\). We have the in-out incident edges \(E_v^{\pm} = \{e\in E\;|\;\partial_{\pm} = v\}\) and the incident edges: \[ E_v = \left\{ \begin{array}{ccc} E_v^+ \sqcup E_v^- & \text{ if } & G \text{ is not symmetric},\\ E_v^- & \text{ if } & G \text{ is symmetric}. \end{array}\right. \]

And we can define the relative weight of a node as the ratio between the weights of the incident edges and the node weight: \[ \rho(v) = \frac{\sum_{e\in E_v}w(e)}{w(v)}. \] If we define the node weight as \(\deg^w(v):= \sum_{e\in E_v}w(e)\), we have what is known as the normalized weight. Note that with this weight \(\rho(v)=1\) for every node \(v\in V\).

\[ \ell^2(V) = \left\{f:V\rightarrow\mathbb{C}\;\left|\;\sum_{v\in V}w(v)|f(v)|^2<+\infty\right.\right\}, \] \[ \ell^2(E) = \left\{\eta:E\rightarrow\mathbb{C}\;\left|\;\sum_{e\in E}w(e)|\eta(e)|^2<+\infty\right.\right\}, \] with respective scalar products for \(f,g\in \ell^2(V)\) and \(\eta,\zeta\in \ell^2(E)\) \[ \langle f, g\rangle = \sum_{v\in V}w(v)f(v)\overline{g(v)}\rangle, \; \text{and} \; \langle \eta, \zeta\rangle = \left\{\begin{array}{ccc} \sum_{e\in E}w(e)\eta(e)\overline{\zeta(e)} & \text{if} & G \text{ is not symmetric},\\ \frac{1}{2}\sum_{e\in E}w(e)\eta(e)\overline{\zeta(e)} & \text{if} & G \text{ is symmetric}. \end{array}\right. \]

Magnetic Laplacian

The magnetic laplacian is the second order derivate of a function \(f\in \ell^2(V)\). The derivate we work with is the twisted derivate \(d_\alpha:\ell^2(V)\rightarrow \ell^2(E)\) that maps \(f\) to \(d_{\alpha}\), s.t. \[ (d_\alpha f)(e) = e^{i\alpha(e)}f(\partial_+ e)-e^{-i\alpha(e)}f(\partial_-e). \] This operator has an adjoint operator \(d_\alpha^*:\ell^2(E)\rightarrow \ell^2(V)\) s.t. \[ (d_\alpha^*\eta)(v) = \frac{1}{w(v)}\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)/2}\overset{\curvearrowright}{\eta_e}(v), \] where \[ \overset{\curvearrowright}{\alpha_e}(v) = \left\{\begin{array}{ccc} -\alpha(e) & \text{if} & v = \partial_-e,\\ \alpha(e) & \text{if} & v = \partial_+e, \end{array}\right.\;\text{ and }\; \overset{\curvearrowright}{\eta_e}(v) = \left\{\begin{array}{ccc} -\eta(e) & \text{if} & v = \partial_-e,\\ \eta(e) & \text{if} & v = \partial_+e. \end{array}\right. \] In Calculations we show that these two operators are adjoint. Since they are adjoint, we can define the autoadjoint operator \(\Delta_\alpha = d_\alpha^*d_\alpha : \ell^2(V)\rightarrow \ell^2(V)\), where \[ \left(\Delta_\alpha f\right)(v) = \rho(v)f(v)-\frac{1}{w(v)}\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)}f(v_e), \] where, \[ v_e = \left\{\begin{array}{ccc} \partial_+e & \text{if} & v = \partial_-e,\\ \partial_-e & \text{if} & v = \partial_+e. \end{array}\right. \]

Tutorial

We seek with specnet to build a comfortable package to work with magnetic graphs (either symmetric or not), the magnetic laplacian, spectral functions, analysis on graphs, build isospectral graphs, etc.

The main object is the MagGraph, a magnetic graph that can be either symmetric or not. If it is symmetric, it automatically add the inverse edges. The potential \(\alpha\) is defined as an edge attribute with key "potential". If it is not specified, it assumes the potential is zero. 

import specnet as spn

G = spn.MagGraph(sym=True)
H = spn.MagGraph(sym=False)

G.add_edge(1, 2, weight=2, potential=1)
H.add_edge(1, 2, weight=2, potential=1)

print(G.edges(data=True))
>>> [(1,2,{'weight':2, 'potential':1}), (2,1,{'weight':2, 'potential':-1})]

print(H.edges(data=True))
>>> [(1,2,{'weight':2, 'potential':1})]

To get the laplacian we use the module specnet.linalg. The Laplacian is a scipy complex sparse array. 

L = spn.linalg.laplacian(G)
type(L)
>>> class 'scipy.sparse._csr.csr_array'

L = spn.linalg.laplacian(G, normalized=True) # normalized version

We built the MagGraph object as a child class of networkx.classes.multidigraph. This way, networkx methods that supports a multidigraph, can support our graph, which give us a lot of freedom.

Calculations

We show that \(d_\alpha\) and \(d_\alpha^*\) are adjoint operators for a non symmetric graph. We recommend do the proof for a symmetric one. \(\forall f\in \ell^2(V)\) and \(\forall \eta\in\ell^2(E)\) we have \[ \begin{align*} \langle d_\alpha f, \eta \rangle &=\sum_{e\in E} w(e)\left(e^{i\alpha(e)/2}f(\partial_+ e)-e^{-i\alpha(e)/2}f(\partial_-e)\right)\overline{\eta(e)}\\ &=\sum_{v\in V}\left[\sum_{e\in E_v^+}\left(w(e)e^{i\alpha(e)/2}f(v)\overline{\eta(e)}\right)-\sum_{e\in E_v^-}\left(w(e)e^{-i\alpha(e)/2}f(v)\overline{\eta(e)}\right)\right]\\ &=\sum_{v\in V}f(v)\overline{\left(\sum_{e\in E_v^+}w(e)e^{-i\alpha(e)/2}\eta(e)-\sum_{e\in E_v^-}w(e)e^{i\alpha(e)/2}\eta(e)\right)}\\ &=\sum_{v\in V}w(v)f(v)\overline{\left(\frac{1}{w(v)}\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)}\overset{\curvearrowright}{\eta_e}(v)\right)}\\ &=\langle f, d_\alpha^*\eta\rangle. \end{align*} \]

To obtain the Laplacian we do: \[ \begin{align*} \left(d_\alpha^*d_\alpha f\right)(v) &=\frac{1}{w(v)}\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)/2}\overset{\curvearrowright}{(d_\alpha f)_e}(v) \\ & = \frac{1}{w(v)}\left(\sum_{e\in E_v^+}w(e)e^{-i\alpha(e)/2}\left(e^{i\alpha(e)/2}f(v)-e^{-i\alpha(e)/2}f(\partial_-e)\right)-\sum_{e\in E_v^-}w(e)e^{i\alpha(e)/2}\left(e^{i\alpha(e)/2}f(\partial_+e)-e^{-i\alpha(e)/2}f(v)\right)\right)\\ &=\frac{1}{w(v)}\left(f(v)\sum_{e\in E_v}w(e)-\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)}f(v_e)\right)\\ &= \rho(v)f(v) -\frac{1}{w(v)}\sum_{e\in E_v}w(e)e^{-i\overset{\curvearrowright}{\alpha_e}(v)}f(v_e) \end{align*} \]

References

  1. Fabila-Carrasco, J.S., Lledó, F. & Post, O. A geometric construction of isospectral magnetic graphs. Anal.Math.Phys. 13, 64 (2023).
  2. Fabila-Carrasco, J.S., Lledó, F., Post, O.: Spectral gaps and discrete magnetic Laplacians. Linear Algebra Appl. 547, 183–216 (2018).