KONECT ‣ Statistics ‣
Buy Me a Coffee
These are the values of the normalized non-bipartivity (bN) for all networks to which the statistic applies and for which it was computed. In total, it has been computed for 414 networks.
The normalized non-bipartivity (bN) 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 normalized symmetric adjacency matrix N. It is defined as one plus the smallest eigenvalue. This is based on the property of the normalized adjacency matrix to have minimal eigenvalue minus one if and only if the graph is bipartite, or to be precise, when there is at least one bipartite connected component. However, in this computation only the largest connected component is taken into account. The value of one is an upper bound, but cannot be attained itself in a loopless graph; this can be seen by considering the trace of the normalized adjacency matrix, which is zero for loopless graphs.
The full definition of the normalized 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 ] |
