Spectral bipartite frustration

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 247 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 at 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.

NameAttributesbK
HIV
0.000 980 636
Zachary karate club
0.047 893 6
Highland tribes
0.081 901 4
Taro exchange
0.074 168 5
Zebra
0.041 816 5
Kangaroos
0.021 128 5
Iceland
0.006 700 16
Contiguous USA
0.027 682 0
Rhesus macaques
0.076 725 5
Dolphins
0.025 759 0
Chesapeake Bay
0.050 112 5
Crisis in a Cloister
0.112 779
Cattle
0.016 074 0
PDZBase
0.000 641 433
Train bombing
0.027 372 3
Sheep
0.054 411 2
Gene fusion
0.001 490 47
Les Misérables
0.009 118 68
Bison
0.080 646 5
David Copperfield
0.022 247 6
Windsurfers
0.089 364 5
Political books
0.037 982 1
Seventh graders
0.090 937 6
Highschool
0.046 827 6
Hens
0.241 935
American football
0.119 066
Similarities (DBpedia)
0.010 491 4
Congress votes
0.018 778 4
Physicians
0.047 336 2
Japanese macaques
0.108 325
Euroroads
0.000 805 549
FilmTrust trust
0.004 082 12
Caenorhabditis elegans (metabolic)
0.008 208 72
Jazz musicians
0.006 253 14
Yeast
0.002 639 85
Little Rock Lake
0.009 088 36
LiquidFeedback (units)
0.001 563 26
Network science
0.023 953 0
Air traffic control
0.001 641 08
Residence hall
0.026 313 3
Facebook (NIPS)
0.000 377 116
A Song of Ice and Fire
0.007 184 18
LiquidFeedback (global)
0.000 867 568
Wikipedia talk (ht)
0.012 301 0
Caenorhabditis elegans
0.008 148 41
Hamsterster households
0.005 801 31
Caenorhabditis elegans (neural)
0.014 586 2
U. Rovira i Virgili
0.008 681 95
Florida ecosystem wet
0.014 707 6
Florida ecosystem dry
0.014 487 1
Dutch college
0.097 525 5
Human proteins (Stelzl)
0.001 643 11
Human proteins (Vidal)
0.005 790 50
Human proteins (Figeys)
0.004 496 47
US power grid
0.001 509 75
Bible
0.023 159 6
Hamsterster friendships
0.000 575 690
Hamsterster friends
0.000 575 690
Route views
0.005 228 29
DNC co-recipients
0.003 767 20
Hamsterster full
0.003 000 91
Adolescent health
0.009 713 80
Blogs
0.003 430 54
LiquidFeedback (issues)
0.004 534 63
LiquidFeedback (areas)
0.004 954 01
Gnutella (08)
0.002 795 52
Sister cities
0.000 914 670
Wikipedia talk (cy)
0.004 467 86
Wikipedia talk (oc)
0.010 905 3
Pretty Good Privacy
0.001 007 21
Gnutella (09)
0.002 651 92
Political blogs
0.002 733 03
Wikipedia talk (br)
0.009 903 76
OpenFlights (Opsahl)
0.001 214 51
Gnutella (06)
0.006 345 13
Gnutella (05)
0.006 940 99
US airports
0.002 815 56
Twitter lists
0.000 443 346
CiaoDVD trust
0.001 851 79
Infectious
0.011 963 6
Gnutella (04)
0.001 386 59
Hypertext 2009
0.006 364 38
Haggle
0.013 349 0
Chicago
0.004 023 08
LiquidFeedback (all)
0.005 168 90
Google+ (NIPS)
0.000 859 765
LiquidFeedback (temporal)
0.005 168 90
Autonomous systems (DIMACS10)
0.004 258 56
CAIDA
0.001 267 92
Gnutella (25)
0.002 835 27
Advogato
0.002 936 84
Wikipedia talk (nds)
0.002 062 78
OpenFlights (Patokallio)
0.001 222 29
Gnutella (24)
0.006 184 77
Filmtipset friendships
0.002 652 64
Wikipedia talk (eo)
0.005 931 62
Gnutella (30)
0.005 945 19
Bitcoin OTC
0.002 490 44
Wikipedia links (lo)
0.000 461 614
Wikipedia links (myv)
0.002 680 18
Cora
0.001 221 48
Wikipedia links (gag)
0.001 085 52
Wikipedia links (am)
0.001 692 34
DBLP
0.002 682 08
Wikipedia links (mi)
0.002 765 72
Wikipedia links (so)
2.686 08 × 10−5
Wikipedia links (vls)
0.002 631 86
Astrophysics
0.002 242 24
JUNG/Javax
0.004 860 33
UC Irvine messages
0.003 357 53
Wikipedia talk (eu)
0.000 833 134
Wikipedia links (bat-smg)
0.002 128 95
Condensed matter (2003)
0.003 792 04
Wikipedia talk (gl)
0.014 311 8
Wikipedia links (crh)
0.000 599 461
Wikipedia links (nds-nl)
0.002 306 98
Java Development Kit
0.004 788 98
Wikipedia links (gv)
0.002 169 68
Wikipedia links (tk)
0.000 584 063
FOLDOC
0.047 775 1
Reactome
0.000 437 614
Chess
0.002 148 26
Wikipedia links (csb)
0.000 556 894
Wikipedia talk (lv)
0.002 753 43
Wikipedia links (wa)
0.003 898 59
Wikipedia links (co)
0.000 117 786
Gnutella (31)
0.005 981 14
Wikipedia links (rue)
0.001 345 66
Wikipedia links (gan)
0.000 451 332
Manufacturing emails
0.002 421 27
Wikipedia links (nah)
0.000 960 406
Google.com internal
0.000 117 648
Wikipedia links (lez)
0.000 760 276
Wikipedia links (as)
0.000 164 992
Wikipedia links (si)
0.000 184 250
Wikipedia links (dv)
0.000 224 540
Condensed matter (2005)
0.002 341 91
arXiv astro-ph
0.001 535 64
Wikipedia links (kv)
0.000 362 616
Digg
0.002 814 78
Wikipedia links (xal)
5.249 89 × 10−5
Wikipedia links (pam)
0.000 471 306
Linux sources
0.000 598 750
Wikipedia links (mhr)
0.001 249 96
Brightkite
0.000 961 582
Wikipedia links (fiu-vro)
0.000 620 367
Wikipedia elections
0.001 446 56
Wikipedia links (ps)
0.000 500 617
Wikipedia links (se)
0.000 342 866
Wikipedia links (hsb)
0.000 778 283
Wikipedia links (fo)
0.001 324 32
Wikipedia links (os)
0.002 847 80
Wikipedia links (diq)
0.000 502 451
Wikipedia links (hif)
0.000 748 756
Wikipedia links (vec)
0.001 221 88
Wikipedia links (cdo)
5.472 47 × 10−6
Wikipedia links (kn)
0.001 043 71
Wikipedia links (glk)
0.000 213 985
Wikipedia links (sah)
0.000 766 905
Slashdot
0.001 428 07
Wikipedia links (gd)
0.001 246 68
Wikipedia links (map-bms)
0.000 501 108
Wikipedia links (bcl)
0.000 398 004
Wikipedia links (bh)
8.815 77 × 10−5
Wikipedia links (li)
0.000 141 260
arXiv hep-th
0.000 633 054
Edinburgh Associative Thesaurus
0.007 915 30
Internet topology
0.001 321 95
Wikipedia links (xmf)
0.000 556 694
Wikipedia links (hak)
0.000 602 995
Wikipedia links (ht)
0.001 326 25
Wikipedia links (nso)
0.000 475 196
arXiv hep-ph
0.001 045 37
EU institution
1.619 04 × 10−5
Wikipedia links (mn)
0.000 326 558
Wikipedia links (arz)
0.000 773 736
Wikipedia links (or)
0.001 097 45
Wikipedia links (pa)
0.000 602 497
Wikipedia links (nds)
0.000 703 215
Wikipedia links (pms)
0.003 396 19
Wikipedia links (yi)
0.000 525 729
Slashdot Zoo
0.001 581 30
Wikipedia links (bar)
0.001 000 23
SAP forums
0.000 784 644
Wikipedia links (io)
0.001 081 59
Wikipedia links (als)
0.001 554 16
WordNet
0.002 198 04
Wikipedia links (ku)
0.000 846 981
Wikipedia links (min)
5.666 89 × 10−5
Wikipedia links (cv)
0.001 423 89
Wikipedia links (vo)
0.002 370 50
Wikipedia links (ky)
0.000 539 899
WikiSigned
0.000 522 891
Wikipedia links (ckb)
0.000 374 429
Wikipedia links (nap)
0.000 305 549
Wikipedia links (roa-tara)
0.000 404 620
Gowalla
0.000 858 003
Wikipedia links (yo)
0.000 103 639
Twitter (ICWSM)
0.000 509 602
Wikipedia links (fy)
0.000 991 088
Wikipedia links (sw)
0.002 016 15
Wikipedia links (is)
0.001 124 29
Wikipedia links (ba)
0.001 025 35
Wikipedia links (su)
0.000 152 507
Wikipedia links (my)
0.000 235 680
Wikipedia links (qu)
0.000 293 636
Wikipedia links (mg)
0.000 369 768
Wikipedia links (ilo)
0.000 708 716
Wikipedia links (scn)
0.000 286 191
Wikipedia links (ast)
0.001 224 39
Wikipedia links (an)
0.000 893 425
Wikipedia links (lb)
0.001 056 19
Wikipedia links (sco)
0.000 681 998
Wikipedia links (mzn)
0.000 259 655
Wikipedia links (gu)
0.000 556 057
Wikipedia links (eml)
0.000 511 941
Wikipedia links (pnb)
0.000 683 217
Facebook (WOSN)
0.000 572 101
Wikipedia links (ga)
0.001 120 48
Wikipedia links (br)
0.001 282 04
Wikipedia links (zh-yue)
0.000 738 859
Epinions
0.000 656 904
Wikipedia links (mr)
0.000 277 583
Notre Dame
3.998 34 × 10−6
Wikipedia links (af)
0.000 706 422
Wikipedia links (new)
0.000 373 947
Wikipedia links (jv)
0.000 749 412
Reality Mining
0.009 327 28
Pennsylvania
0.000 183 671
Facebook
0.001 767 33
CiteSeer
0.000 262 563
Wikipedia links (ia)
0.000 287 906
Wikipedia links (ml)
0.000 948 833
Flickr
0.001 517 36
Wikipedia links (bpy)
9.198 82 × 10−5
Enron
8.928 20 × 10−5
Texas
0.000 197 445
Stanford
2.329 50 × 10−5
Baidu related
0.000 183 288
arXiv hep-th
0.000 273 859
Wikipedia dynamic (simple)
0.000 833 824
California
7.347 08 × 10−5
Amazon (TWEB, 0601)
0.001 310 62
Catster
0.000 367 287
Wikipedia messages (en)
0.002 039 98
Youtube links
0.000 202 583
arXiv hep-ph
0.000 424 561