Exploring deeper understanding and better description of networks

Exploring deeper understanding and better description of networks
Totally homogeneous network examples: A tetrahedron, a minimal 2-cavity network, an 8-node nearest-neighbor network, and a 10-node synchronization-optimal network Credit: Science China Press

Since the beginning of the last century, research on complex systems has advanced the fields of chaos, fractals and networks. A network consists of nodes and edges, where nodes represent the elements of a complex system and edges describe the interactions among them. Such node-edge relations can be represented by an adjacency matrix, whose order equals the number of nodes and each row-sum corresponds to a node degree. The heterogeneity of node degrees leads to the emergence of star-shaped structures centered at hub nodes.

To address the heterogeneity of node degrees, the scale-free network model came into play, attracting broad attention. To date, as internet technology advances and network research proceeds, researchers have realized that the traditional perception about star-based heterogeneous networks is insufficient to describe evolving complex networks and and network-scientific problems. For instance, there are many online communities on the internet that depend on cycle-based social structures for group communication and information spreading.

Network functioning and dynamical properties have more and closer connections with higher-order network topological features, homogeneous substructures and topological invariants. Thus, shifting the focus from node degrees to cycle numbers reveals many totally homogeneous subnetworks in . Here, a totally homogeneous network is defined to be a network with nodes having same degree, same girth (number of edges in the smallest cycle of a node), and same path-sum (sum of shortest paths to a node from all other nodes). A few typical examples are shown in Figure 1 for illustration.

At the end of the 19th century, Poincaré found that boundaries are key in differentiating geometric shapes such as disks, spheres and tori. He decomposed a geometric object into basic components called simplexes (point, line, triangle, tetrahedron, etc.), and then introduced the concepts of homology grouping, Betti number and node-edge correlation matrix, and the Euler-Poincaré formula, which shows that the alternative summation of simplexes equals the alternative summation of Betti numbers.

Poincaré's basic idea is to split a complex geometric shape so as to simplify the procedure for a solution. He was able to do so because there are many totally homogeneous subnetworks, such as triangles and tetrahedrons (referred to as cliques in graph theory or simplexes in topology) in a complex network. They are basic structures for supporting network functions—differing from stars, they are cycles. With these basic elements, it is possible to describe a network using a series of vector spaces over the binary field.

For example, the vector space has edges as its basis, with dimension equal to the number of edges; the vector space has triangles as its basis, with dimension equal to the number of triangles, and so on. Since the boundary of a triangle consists of edges, the two adjacent vector spaces and can be correlated via a boundary operator, and its boundary matrix can be used for presentation and analysis. The boundary matrix has richer mathematical content and is more useful than the adjacency matrix. For instance, using the rank of the boundary matrix one can compute the Betti number, an important invariant of the network, which is the number of linearly independent cavities of different orders in the network, establishing a homology group. Figure 2 shows the relationships of some vector spaces and their corresponding boundary operators.

In 2002, Xiaofan Wang and Guanrong Chen published the first criterion of network synchronization. It was followed by a series of works including the introduction of totally homogenous networks via optimization by Dinghua Shi, Guanrong Chen and Xiaoyong Yan in 2013, revealing that the totally homogenous network with a longer girth and a shorter path-sum has a better synchronizability among networks of the same size. In addition, in 2006, Linyuan Lü and Tao Zhou used the H-operator to uncover the relationship among node degree, H-index and kernel value, establishing the DHC theorem. In the investigation of cycle index, an important work is the empirical study of Bassett et al. in 2018 on the brain functional network, in which they pointed out the importance of cliques and cavities in network functioning. Last but not least, we recently discovered the close relationship of Euler characteristic numbers to network synchronizability.

This series of important progressive results demonstrates the significance and importance of interdisciplinary research in physics, biology and mathematics. Considering that this new direction of structural analysis using algebraic topological tools is promising, the researchers chose to publish their current paper, "Totally homogeneous networks," in National Science Review.

Exploring deeper understanding and better description of networks
Relationships of some vector spaces and their corresponding boundary operators (Zk is a cycle group, Yk is a boundary group) Credit: Science China Press

Explore further

A friend of a friend is... a dense network

More information: Dinghua Shi et al, Totally Homogeneous Networks, National Science Review (2019). DOI: 10.1093/nsr/nwz050
Citation: Exploring deeper understanding and better description of networks (2019, June 5) retrieved 19 July 2019 from https://phys.org/news/2019-06-exploring-deeper-description-networks.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
9 shares

Feedback to editors

User comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more