Complex network zeta function: Difference between revisions

Revision as of 17:42, 1 February 2012

Latest revision as of 10:43, 12 November 2024

(6 intermediate revisions by 6 users not shown)

Line 1:

Different definitions have been given for the dimension of a [[complex network]] or [[graph theory|graph]]. For example, [[Metric dimension (graph theory)|metric dimension]] is defined in terms of the resolving set for a graph. Dimension has also been [[Fractal dimension on networks|defined]] based on the [[Minkowski–Bouligand dimension|box covering method]] applied to graphs.<ref name=goh>{{cite journal | last1=Goh | first1=K.-I. Goh,| last2=Salvi | first2=G. Salvi,| last3=Kahng | first3=B. Kahng| andlast4=Kim | first4=D. Kim,| Phystitle=Skeleton and Fractal Scaling in Complex Networks | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=96 | issue=1 | date=2006-01-11 | issn=0031-9007 | doi=10.1103/physrevlett.96.018701 | page=018701| pmid=16486532 |arxiv=cond-mat/0508332}}</ref> Here we describe the definition based on the '''complex network zeta function'''.<ref name="Shankerb">{{cite journal|author=O. Shanker|year=2007|title=Graph Zeta Function and Dimension of Complex Network|journal=Modern Physics Letters B|volume= 21|pages=639–644|doi=10.1142/S0217984907013146 | issue=11|bibcode=2007MPLB...21..639S}}</ref> This generalises the definition based on the scaling property of the volume with distance.<ref name="Shankera">{{cite journal|author=O. Shanker|year=2007|title=Defining Dimension of a Complex Network |journal=Modern Physics Letters B|volume= 21|pages=321–326|doi=10.1142/S0217984907012773 | issue=6|bibcode=2007MPLB...21..321S}}</ref> The best definition depends on the Revapplication.

Lett. 96, 018701 (2006).</ref>. Here we describe the definition based on the '''complex network zeta function'''<ref name="Shankerb">{{cite journal|author=O. Shanker|year=2007|title=Graph Zeta Function and Dimension of Complex Network|journal=Modern Physics Letters B|volume= 21|pages=639–644|doi=10.1142/S0217984907013146 | issue=11|bibcode=2007MPLB...21..639S}}</ref>. This generalises the definition based on the scaling property of the volume with distance<ref name="Shankera">{{cite journal|author=O. Shanker|year=2007|title=Defining Dimension of a Complex Network |journal=Modern Physics Letters B|volume= 21|pages=321–326|doi=10.1142/S0217984907012773 | issue=6|bibcode=2007MPLB...21..321S}}</ref>. The best definition depends on the application.

==Definition==

One usually thinks of dimension for a set which is dense, like the points on a line, for example. Dimension makes sense in a discrete setting, like for graphs, only in the large system limit, as the size tends to infinity. For example, in Statistical Mechanics, one considers discrete points which are located on regular lattices of different dimensions. Such studies have been extended to arbitrary networks, and it is interesting to consider how the definition of dimension can be extended to cover these cases. A very simple and obvious way to extend the definition of dimension to arbitrary large networks is to consider how the volume (number of nodes within a given distance from a specified node) scales as the distance (shortest path connecting two nodes in the graph) is increased. For many systems arising in physics, this is indeed a useful approach. This definition of dimension could be put on a strong mathematical foundation, similar to the definition of Hausdorff dimension for continuous systems. The mathematically robust definition uses the concept of a zeta function for a graph. The complex network zeta function and the graph surface function were introduced to characterize large graphs. They have also been applied to study patterns in Language Analysis. In this section we will briefly review the definition of the functions and discuss further some of their properties which follow from the definition.

We denote by <math> \textstyle r_{ij} </math> the distance from node <math>\textstyle i</math> to node <math>\textstyle j</math>, i.e., the length of the shortest path connecting the first node to the second node. <math>\textstyle r_{ij}</math> is <math>\textstyle \infty</math> if there is no path from node <math>\textstyle i</math> to node <math>\textstyle j</math>. With this definition, the nodes of the complex network become points in a [[metric space]].<ref name="Shankerb"/>. Simple generalisations of this definition can be studied, e.g., we could consider weighted edges. The graph surface function, <math>\textstyle S(r )</math>, is defined as the number of nodes which are exactly at a distance <math> \textstyle r </math> from a given node, averaged over all nodes of the network. The complex network zeta function <math>\textstyle \zeta_G ( \alpha )</math> is defined as

:<math> \zeta_G ( \alpha ) := \frac{1}{N}\sum_i \sum_{j\neq i }r^{-\alpha}_{ij}, </math>

Line 14 ⟶ 13:

:<math> \langle k \rangle = \lim_{\alpha \rightarrow \infty} \zeta_G ( \alpha ). </math>

The need for taking an average over all nodes can be avoided by using the concept of supremum over nodes, which makes the concept much easier to apply for formally infinite graphs.<ref name="ShankerTCS">{{cite journal|author=O. Shanker|year=2010|title=Complex Network Dimension and Path Counts|journal=Theoretical Computer Science|volume= 411|pages=2454–2458|doi=10.1016/j.tcs.2010.02.013|issue=26–28|doi-access=free}}</ref>. The definition can be expressed as a weighted sum over the node distances. This gives the Dirichlet series relation

:<math> \zeta_G ( \alpha ) = \sum_r S(r)/r^{\alpha}. </math>

Line 25 ⟶ 24:

:<math> \|\vec{n}\|_1=\|n_1\|+\cdots +\|n_d\|, </math>

the transition occurs at <math>\textstyle \alpha = d</math>. The definition of dimension using the complex network zeta function satisfies properties like monotonicity (a subset has a lower or the same dimension as its containing set), stability (a union of sets has the maximum dimension of the component sets forming the union) and Lipschitz invariance ,<ref name=falconer>[[Kenneth Falconer (mathematician)|K. Falconer.]], Fractal Geometry: Mathematical Foundations and Applications, Wiley, second edition, 2003</ref>, provided the operations involved change the distances between nodes only by finite amounts as the graph size <math>\textstyle N</math> goes to <math>\textstyle \infty</math>. Algorithms to calculate the complex network zeta function have been presented.<ref name="Shankerc">{{cite journal|author=O. Shanker, |year=2008|title=Algorithms for Fractal Dimension Calculation|journal=Modern Physics Letters B|volume= 22|pages=459–466|doi=10.1142/S0217984908015048|issue=7|bibcode=2008MPLB...22..459S}}</ref>.

==Values for discrete regular lattices==

For a one-dimensional regular lattice the graph surface function <math>\textstyle S_{1}(r)</math> is exactly two for all values of <math>\textstyle r</math> (there are two nearest neighbours, two next-nearest neighbours, and so on). Thus, the complex network zeta function <math>\textstyle \zeta_G ( \alpha )</math> is equal to <math>\textstyle 2\zeta(\alpha)</math>, where <math>\textstyle \zeta(\alpha)</math> is the usual Riemann zeta function. By choosing a given axis of the lattice and summing over cross-sections for the allowed range of distances along the chosen axis the recursion relation below can be derived

:<math> S_{d+1}(r) = 2+S_d (r)+2\sum^{r-1}_{i=1}S_d(i). </math>

Line 66 ⟶ 65:

==References==

{{Reflist}}

<references/>

[[Category:GraphAlgebraic graph theory]]

[[Category:Dimension]]

[[Category:Network theory]]