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 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 ]

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
Pro League (2016/2017)
0.194 302
Train bombing
0.027 372 3
Sheep
0.054 411 2
Gene fusion
0.001 490 47
Les Misérables
0.009 118 68
Bundesliga (2016/2017)
0.188 882
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
Ligue 1 (2016/2017)
0.203 142
Premier League (2013/2014)
0.181 865
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
Erdős
0.001 791 80
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
Bitcoin Alpha
0.002 435 24
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
Cora
0.001 221 48
Wikipedia links (gag)
0.001 086 57
Wikipedia links (lo)
0.000 553 583
DBLP
0.002 682 08
Wikipedia links (am)
0.001 719 40
Wikipedia links (mi)
0.002 770 26
Wikipedia links (so)
0.001 154 41
Astrophysics
0.002 242 24
Wikipedia links (vls)
0.002 592 09
JUNG/Javax
0.004 860 33
UC Irvine messages
0.003 357 53
Wikipedia talk (eu)
0.000 833 134
Condensed matter (2003)
0.003 792 04
Wikipedia links (bat-smg)
0.002 127 41
Wikipedia talk (gl)
0.014 311 8
Wikipedia links (nds-nl)
0.002 318 82
Java Development Kit
0.004 788 98
Wikipedia links (myv)
0.002 462 45
Wikipedia links (gv)
0.002 170 25
Wikipedia links (tk)
0.000 586 202
FOLDOC
0.047 775 1
Reactome
0.000 437 614
Chess
0.002 148 26
Wikipedia links (csb)
0.000 558 693
Wikipedia talk (lv)
0.002 753 43
Wikipedia links (crh)
0.000 518 521
Wikipedia links (wa)
0.003 858 60
Gnutella (31)
0.005 981 14
Wikipedia links (co)
0.000 118 068
Wikipedia links (gan)
0.000 452 097
Manufacturing emails
0.002 421 27
Wikipedia links (nah)
0.000 750 628
Wikipedia links (rue)
0.001 298 20
Google.com internal
0.000 117 648
Wikipedia links (lez)
0.000 744 905
Wikipedia links (dv)
0.000 224 687
Condensed matter (2005)
0.002 341 91
Wikipedia links (as)
0.000 172 898
arXiv astro-ph
0.001 535 64
Wikipedia links (si)
0.000 186 963
Wikipedia links (kv)
0.000 358 129
Digg
0.002 814 78
Wikipedia links (xal)
5.115 28 × 10−5
Wikipedia links (pam)
0.000 470 164
Linux sources
0.000 598 750
Wikipedia links (mhr)
0.001 200 54
Brightkite
0.000 961 582
Wikipedia links (fiu-vro)
0.000 625 308
Wikipedia elections
0.001 446 56
Wikipedia links (se)
0.000 515 071
Wikipedia talk (bn)
0.002 638 66
Wikipedia links (fo)
0.001 322 23
Wikipedia links (hsb)
0.000 778 331
Wikispeedia
0.006 417 68
Wikipedia links (os)
0.002 840 92
Wikipedia talk (sk)
0.004 366 08
Wikipedia links (hif)
0.000 750 609
Wikipedia links (diq)
0.000 498 772
Wikipedia links (vec)
0.001 221 07
Wikipedia links (cdo)
2.217 18 × 10−6
Wikipedia links (glk)
0.000 213 915
Wikipedia links (kn)
0.000 784 464
Slashdot
0.001 428 07
Wikipedia links (sah)
0.000 359 432
Wikipedia links (map-bms)
0.000 501 884
Wikipedia links (bcl)
0.000 494 812
Wikipedia links (gd)
0.001 224 71
arXiv hep-th
0.000 633 054
Wikipedia links (bh)
0.000 365 385
Edinburgh Associative Thesaurus
0.007 915 30
Internet topology
0.001 321 95
Wikipedia links (li)
0.000 138 993
Wikipedia links (xmf)
0.000 558 449
Douban
0.001 112 21
Wikipedia talk (el)
0.003 406 57
Wikipedia links (hak)
0.000 613 252
Wikipedia links (ht)
0.001 402 49
Wikipedia links (nso)
0.000 475 488
arXiv hep-ph
0.001 045 37
EU institution
1.619 03 × 10−5
Wikipedia links (mn)
0.000 325 560
Wikipedia links (arz)
0.000 767 947
Wikipedia links (or)
0.001 093 46
Epinions
0.000 753 884
Wikipedia links (pa)
0.000 410 797
Wikipedia links (nds)
0.000 723 251
Wikipedia links (ps)
0.000 229 129
Catster households
0.001 440 85
Wikipedia links (pms)
0.003 755 07
Wikipedia talk (sr)
0.002 193 01
Wikipedia links (yi)
0.000 522 474
Slashdot Zoo
0.001 581 69
SAP forums
0.000 784 644
Wikipedia links (bar)
0.000 628 166
Wikipedia talk (ca)
0.007 793 52
WordNet
0.002 198 04
Wikipedia links (als)
0.001 525 61
Wikipedia links (io)
0.001 022 40
Wikipedia links (ku)
0.000 843 336
Wikipedia links (min)
5.713 37 × 10−5
Wikipedia links (vo)
0.002 366 89
Wikipedia links (cv)
0.001 397 04
New York City
0.000 141 331
Wikipedia links (ky)
0.000 595 448
WikiSigned
0.000 522 891
Wikipedia links (nap)
0.000 305 939
San Francisco Bay Area
4.346 47 × 10−5
Wikipedia links (roa-tara)
0.000 405 190
Gowalla
0.000 858 003
Wikipedia links (yo)
0.000 106 335
Twitter (ICWSM)
0.000 509 603
MathOverflow
0.003 028 19
Wikipedia links (fy)
0.000 988 846
Wikipedia links (ckb)
0.000 334 076
Amazon (MDS)
0.001 185 21
Wikipedia links (sw)
0.002 011 38
Wikipedia links (is)
0.001 113 65
Wikipedia links (mg)
0.000 380 714
Wikipedia links (my)
0.000 399 990
Wikipedia links (su)
0.000 175 393
Wikipedia links (qu)
0.000 294 378
Wikipedia links (ba)
0.001 038 77
Wikipedia talk (sv)
0.009 971 48
Wikipedia links (ilo)
0.000 710 817
Wikipedia links (scn)
0.000 286 926
DBLP co-authorship
0.002 175 53
Colorado
3.877 48 × 10−5
Wikipedia talk (vi)
0.001 467 47
Wikipedia links (an)
0.000 887 565
Wikipedia links (mzn)
0.000 239 229
Wikipedia links (lb)
0.001 030 36
Wikipedia links (gu)
0.000 552 832
Wikipedia links (pnb)
0.000 694 119
Facebook (WOSN)
0.000 572 139
Wikipedia links (sco)
0.000 693 951
Amazon (TWEB, 0302)
0.002 439 56
Wikipedia links (eml)
0.000 510 801
Wikipedia links (ga)
0.001 144 79
Wikipedia links (br)
0.001 275 86
Wikipedia links (zh-yue)
0.000 732 701
Epinions
0.000 656 904
Notre Dame
4.040 25 × 10−6
Wikipedia links (mr)
0.000 720 598
Wikipedia links (new)
0.000 373 981
Wikipedia links (jv)
0.000 769 388
Reality Mining
0.009 327 28
Pennsylvania
0.000 183 671
Facebook
0.001 767 33
CiteSeer
0.000 262 567
Wikipedia links (af)
0.000 680 463
Wikipedia links (ia)
0.000 290 640
Wikipedia links (ast)
0.001 021 23
Ask Ubuntu
0.001 856 31
Linux kernel mailing list replies
5.197 43 × 10−5
Wikipedia talk (ja)
0.004 189 78
Wikipedia links (ml)
0.000 937 571
Flickr
0.001 517 36
Wikipedia links (bpy)
9.289 36 × 10−5
Enron
8.928 20 × 10−5
Wikipedia links (tl)
0.000 114 242
Livemocha
0.001 008 27
Texas
0.000 197 445
Stanford
2.329 34 × 10−5
Dogster households
0.001 796 49
Wikipedia links (sq)
0.000 506 492
Wikipedia links (be-x-old)
0.001 153 98
Wikipedia talk (pl)
0.004 392 51
Wikipedia links (ne)
2.061 71 × 10−5
Wikipedia links (bn)
0.000 104 597
Wikipedia links (te)
0.000 461 329
Wikipedia links (cy)
0.001 225 59
Wikipedia talk (nl)
0.002 293 82
Catster/dogster households
0.001 279 87
Super User
0.001 965 33
Italian CNR
3.108 00 × 10−6
Yahoo advertisers
0.019 918 4
Baidu related
0.000 183 288
Florida
3.485 61 × 10−5
Youtube friendships
0.000 202 579
arXiv hep-th
0.000 273 859
Northwest USA
3.169 53 × 10−5
Wikipedia dynamic (simple)
0.000 833 824
Hyves
0.002 536 64
California
7.347 08 × 10−5
Wikipedia links (lmo)
0.000 495 641
Amazon (TWEB, 0312)
0.001 354 97
Wikipedia links (lv)
0.001 312 08
Wikipedia links (nn)
0.000 641 371
Wikipedia links (la)
0.000 657 500
Digg friends
0.000 240 148
Wikipedia links (sa)
0.000 101 204
Amazon (TWEB, 0505)
0.001 158 18
Amazon (TWEB, 0601)
0.001 310 62
Wikipedia talk (ar)
0.002 173 87
Wikipedia links (uz)
0.000 169 523
Wikipedia talk (ru)
0.005 593 42
Wikipedia links (az)
0.001 039 94
Wikipedia links (zh-min-nan)
0.000 247 197
Wikipedia talk (pt)
0.001 492 80
Catster
0.000 367 287
Wikipedia threads (de)
0.001 077 10
Northeast USA
7.679 10 × 10−5
Wikipedia links (tt)
9.301 06 × 10−5
Wikipedia talk (zh)
0.002 671 72
Wikipedia links (mk)
0.000 363 855
Wikipedia links (ka)
0.000 740 629
Wikipedia links (simple)
0.000 611 736
Wikipedia talk (es)
0.002 352 25
Wikipedia links (et)
0.001 233 96
Wikipedia messages (en)
0.002 039 97
Wikipedia links (bug)
3.477 08 × 10−5
Wikipedia links (tg)
0.000 187 531
Google hyperlinks
9.439 92 × 10−5
Youtube links
0.000 202 591
California and Nevada
3.677 17 × 10−5
Catster friends
0.000 369 755
Wikipedia links (el)
0.000 600 400
Wikipedia talk (it)
0.004 722 98
Wikipedia links (th)
0.000 727 261
Wikipedia links (lt)
0.001 299 24
Wikipedia links (be)
0.001 269 58
Prosper loans
0.001 223 38
arXiv hep-ph
0.000 424 561
Wikipedia links (ce)
0.000 524 222
Wikipedia links (hr)
0.000 945 296
Wikipedia links (ta)
0.000 448 198
Wikipedia links (hi)
0.000 200 999
Berkeley/Stanford
1.644 81 × 10−5
Dogster
0.000 638 664
Wikipedia links (sl)
0.000 981 354
Great Lakes
1.431 10 × 10−5
Wikipedia talk (fr)
0.001 829 73
Flixster
0.000 802 782
Wikipedia links (eu)
0.000 313 240
Dogster friends
0.000 638 889
TREC WT10g
1.183 14 × 10−5
Wikipedia links (bg)
0.000 424 807
Wikipedia conflict
0.000 836 416
Wikipedia links (da)
0.000 859 231
Eastern USA
1.762 70 × 10−5
Wikipedia links (bs)
0.000 394 697
Wikipedia talk (de)
0.001 349 57
Higgs
0.000 415 976
Wikipedia links (kk)
0.000 390 394
Wikipedia links (tr)
0.000 520 985
Flickr links
4.791 87 × 10−5
Indian domain
1.506 54 × 10−6
Hudong internal
3.068 41 × 10−5
DBpedia
2.626 81 × 10−5
European Union domain
1.203 39 × 10−6
Baidu internal
9.639 83 × 10−5
Western USA
1.281 31 × 10−5
Wikipedia links (cs)
0.000 662 015
US patents
0.000 451 120
Wikipedia links (hy)
0.000 607 271
Wikipedia links (oc)
7.258 16 × 10−5
Twitter mentions
6.019 94 × 10−5
Actor collaborations
0.000 735 675
Central USA
1.465 95 × 10−5
Wikipedia talk (en)
0.002 707 63
Wikipedia links (vi)
0.000 686 883
LiveJournal links
0.000 150 806
DBLP
0.001 123 70
Flickr
4.229 84 × 10−5
Wikipedia links (ar)
0.000 253 465
Wikipedia growth (en)
0.000 256 124
Stack Overflow
0.000 957 115