Meshedness coefficient

Last updated April 24, 2019

In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices. It ranges from 0 for trees to 1 for maximal planar graphs.^[1]^[2]

Graph theory Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In mathematics, and, more specifically, in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa. A forest is a disjoint union of trees, or equivalently an acyclic graph that is not necessarily connected.

Definition

The meshedness coefficient is used to compare the general cycle structure of a connected planar graph to two extreme relevant references. In one end, there are trees, planar graphs with no cycle.^[1] The other extreme is represented by maximal planar graphs, planar graphs with the highest possible number of edges and faces for a given number of vertices. The normalized meshedness coefficient is the ratio of available face cycles to the maximum possible number of face cycles in the graph. This ratio is 0 for a tree and 1 for any maximal planar graph.

More generally, it can be shown using the Euler characteristic that all n-vertex planar graphs have at most 2n − 5 bounded faces (not counting the one unbounded face) and that if there are m edges then the number of bounded faces is m − n + 1 (the same as the circuit rank of the graph). Therefore, a normalized meshedness coefficient can be defined as the ratio of these two numbers:

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by $.$

Circuit rank the minimum number of edges to remove from a graph to eliminate all its cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. Alternatively, it can be interpreted as the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank $r$ is easily computed using the formula

\alpha ={\frac {m-n+1}{2n-5}}.

It varies from 0 for trees to 1 for maximal planar graphs.

Applications

The meshedness coefficient can be used to estimate the redundancy of a network. This parameter along with the algebraic connectivity which measures the robustness of the network, may be used to quantify the topological aspect of network resilience in water distribution networks.^[3] It has also been used to characterize the network structure of streets in urban areas.^[4]^[5]^[6]

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analysing the robustness and synchronizability of networks.

Limitations

Using the definition of the average degree $\langle k\rangle =2m/n$ , one can see that in the limit of large graphs (number of edges $n\gg 1$ ) the meshedness tends to

\alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}

Thus, for large graphs, the meshedness does not carry more information than the average degree.

Related Research Articles

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its Eulerian subgraphs.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the cycle space of the graph has a cycle basis in which each edge of the graph participates in at most two basis vectors.

In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In combinatorics, the Eulerian numberA(n, m), is the number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element. They are the coefficients of the Eulerian polynomials:

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the world wide web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert and is a special case of a more general model called Price's model.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Modularity is one measure of the structure of networks or graphs. It was designed to measure the strength of division of a network into modules. Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity.

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In mathematics, specifically group theory, a descendant tree is a hierarchical structure for visualizing parent-descendant relations between isomorphism classes of finite groups of prime power order $, for a fixed prime number and varying integer exponents . Such groups are briefly called finite p-groups . The vertices of a descendant tree are isomorphism classes of finite p -groups.$

The structural cut-off is a concept in network science which imposes a degree cut-off in the degree distribution of a finite size network due to structural limitations. Networks with vertices with degree higher than the structural cut-off will display structural disassortativity.

In network science, the efficiency of a network is a measure of how efficiently it exchanges information. The concept of efficiency can be applied to both local and global scales in a network. On a global scale, efficiency quantifies the exchange of information across the whole network where information is concurrently exchanged. The local efficiency quantifies a network's resistance to failure on a small scale. That is the local efficiency of a node $characterizes how well information is exchanged by its neighbors when it is removed.$

In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.

In network science, the configuration model is a method for generating random networks from given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the user to incorporate arbitrary degree distributions.

Maximum-entropy random graph models are random graph models used to study complex networks subject to the principle of maximum entropy under a set of structural constraints , which may be global, distributional, or local.

References

1 2 Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004). "Efficiency and robustness in ant networks of galleries". The European Physical Journal B. 42 (1): 123–129. doi:10.1140/epjb/e2004-00364-9.
↑ Buhl, J.; Gautrais, J.; Reeves, N.; Sole, R.V.; Valverde, S.; Kuntz, P.; Theraulaz, G. (2006). "Topological patterns in street networks of self-organized urban settlements". The European Physical Journal B. 49 (4): 513–522. doi:10.1140/epjb/e2006-00085-1.
↑ Yazdani, A.; Jeffrey, P. (2012). "Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems". Journal of Water Resources Planning and Management. 138 (2): 153–161. doi:10.1061/(ASCE)WR.1943-5452.0000159.
↑ Wang, X.; Jin, Y.; Abdel-Aty, M.; Tremont, P.J.; Chen, X. (2012). "Macrolevel Model Development for Safety Assessment of Road Network Structures". Transportation Research Record: Journal of the Transportation Research Board. 2280 (1): 100–109. doi:10.3141/2280-11. Archived from the original on 2014-11-21.
↑ Courtat, T.; Gloaguen, C.; Douady, S. (2011). "Mathematics and morphogenesis of cities: A geometrical approach". Phys. Rev. E. 83 (3): 036106. arXiv: 1010.1762 . doi:10.1103/PhysRevE.83.036106. PMID 21517557.
↑ Rui, Y.; Ban, Y.; Wang, J.; Haas, J. (2013). "Exploring the patterns and evolution of self-organized urban street networks through modeling". The European Physical Journal B. 86 (3): 036106. doi:10.1140/epjb/e2012-30235-7.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[first-1] 1 2 Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004). "Efficiency and robustness in ant networks of galleries". The European Physical Journal B. 42 (1): 123–129. doi:10.1140/epjb/e2004-00364-9.

[Second-2] Buhl, J.; Gautrais, J.; Reeves, N.; Sole, R.V.; Valverde, S.; Kuntz, P.; Theraulaz, G. (2006). "Topological patterns in street networks of self-organized urban settlements". The European Physical Journal B. 49 (4): 513–522. doi:10.1140/epjb/e2006-00085-1.

[Third-3] Yazdani, A.; Jeffrey, P. (2012). "Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems". Journal of Water Resources Planning and Management. 138 (2): 153–161. doi:10.1061/(ASCE)WR.1943-5452.0000159.

[Fourth-4] Wang, X.; Jin, Y.; Abdel-Aty, M.; Tremont, P.J.; Chen, X. (2012). "Macrolevel Model Development for Safety Assessment of Road Network Structures". Transportation Research Record: Journal of the Transportation Research Board. 2280 (1): 100–109. doi:10.3141/2280-11. Archived from the original on 2014-11-21.

[Fifth-5] Courtat, T.; Gloaguen, C.; Douady, S. (2011). "Mathematics and morphogenesis of cities: A geometrical approach". Phys. Rev. E. 83 (3): 036106. arXiv: 1010.1762 . doi:10.1103/PhysRevE.83.036106. PMID 21517557.

[Sixth-6] Rui, Y.; Ban, Y.; Wang, J.; Haas, J. (2013). "Exploring the patterns and evolution of self-organized urban street networks through modeling". The European Physical Journal B. 86 (3): 036106. doi:10.1140/epjb/e2012-30235-7.