KONECT ‣ Statistics ‣
Buy Me a Coffee
These are the values of the non-bipartivity (bA) for all networks to which the statistic applies and for which it was computed. In total, it has been computed for 418 networks.
The non-bipartivity (bA) measures to what extent a graph deviates from a bipartite graph. The non-bipartivity applies to all graphs in KONECT that are not bipartite, as for bipartite graphs, it is by definition zero. The non-bipartivity is a number between zero and one, equalling zero for bipartite graphs, and one for maximally non-bipartite graphs. There are multiple measures of (non-)bipartivity possible, and this measure is based on the spectrum of the symmetric adjacency matrix A. It is defined as one minus the absolute value of the smallest eigenvalue divided by the largest eigenvalue. This is based on the property of the adjacency matrix to have matching maximal and minimal eigenvalues if and only if the graph is bipartite, or to be precise, when the connected component with the largest spectral norm is bipartite. The value of one is an upper bound, but cannot be attained itself in a loopless graph; this can be seen by the fact that the sum of eigenvalues of the symmetric adjacency matrix equals the number of loops in the graph. We recommend this statistic as the default measure of (non-)bipartivity, as it is fast to compute even for large graphs, it correlates well with other measures, and its values are well distributed in its range.
The full definition of the non-bipartivity as well as its properties and relationships to other graph statistics can be found in the KONECT handbook.
References for this statistic:
| [1] | Jérôme Kunegis. Exploiting the structure of bipartite graphs for algebraic and spectral graph theory applications. Internet Math., 11(3):201–321, 2015. [ http ] |
