KONECT ‣ Statistics ‣
Buy Me a Coffee
These are the values of the spectral bipartite frustration (bK) for all networks to which the statistic applies and for which it was computed. In total, it has been computed for 371 networks.
The spectral bipartite frustration (bK) is a measure of non-bipartivity of a 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 smallest eigenvalue of the signless Laplacian matrix K = D + A. The measure is defined as the smallest eigenvalue of that matrix (which is always nonnegative because the matrix is positive-semidefinite), multiplied by the number of nodes, and divided by eight times the number of edges. This way to scale the smallest eigenvalues gives a value between zero and one. The smallest eigenvalue (and thus the measure) is zero if and only if the graph has at least one bipartite connected component. In KONECT, we restrict the computation to each graph's largest connected component. The measure can be interpreted as an approximation to the fraction of edges that must be removed from the graph to make it bipartite. It is analogous to the spectral signed frustration applied to the corresponding network with all negative edges.
The full definition of the spectral bipartite frustration 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 ] |
