Non-bipartivity

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 ]

NameAttributesbA
HIV
0.000 324 537
Zachary karate club
0.332 823
Highland tribes
0.561 989
Taro exchange
0.280 755
Zebra
0.748 511
Kangaroos
0.765 565
Iceland
0.324 454
Contiguous USA
0.456 938
Rhesus macaques
0.645 909
Dolphins
0.468 830
Chesapeake Bay
0.374 781
Crisis in a Cloister
0.727 559
Cattle
0.722 318
PDZBase
0.000 152 507
Pro League (2016/2017)
0.777 520
Train bombing
0.655 074
Sheep
0.755 225
Gene fusion
0.000 835 519
Les Misérables
0.561 283
Bundesliga (2016/2017)
0.771 061
Bison
0.790 714
David Copperfield
0.420 969
Windsurfers
0.724 591
Political books
0.564 121
Seventh graders
0.736 441
Ligue 1 (2016/2017)
0.797 627
Premier League (2013/2014)
0.795 621
Highschool
0.605 910
Hens
0.967 742
American football
0.579 913
Similarities (DBpedia)
0.676 315
Congress votes
0.332 336
Physicians
0.510 672
Japanese macaques
0.811 084
Euroroads
0.061 239 9
FilmTrust trust
0.438 526
Caenorhabditis elegans (metabolic)
0.429 332
Jazz musicians
0.782 583
Yeast
0.006 130 51
Little Rock Lake
0.435 995
LiquidFeedback (units)
0.000 637 989
Network science
0.712 488
Air traffic control
0.320 044
Residence hall
0.664 996
Facebook (NIPS)
0.002 518 41
A Song of Ice and Fire
0.578 642
LiquidFeedback (global)
6.270 78 × 10−5
Wikipedia talk (ht)
0.872 451
Caenorhabditis elegans
0.301 910
Hamsterster households
0.565 705
Caenorhabditis elegans (neural)
0.473 226
U. Rovira i Virgili
0.592 240
Florida ecosystem wet
0.494 702
Florida ecosystem dry
0.490 948
Dutch college
0.745 563
Human proteins (Stelzl)
0.032 266 0
Human proteins (Vidal)
0.186 364
Human proteins (Figeys)
0.047 786 8
US power grid
0.398 772
Bible
0.491 978
Hamsterster friendships
0.478 324
Erdős
0.301 002
Hamsterster friends
0.478 324
Route views
0.176 419
DNC co-recipients
0.755 203
Hamsterster full
0.602 303
Adolescent health
0.548 498
Blogs
0.634 253
LiquidFeedback (issues)
0.558 222
LiquidFeedback (areas)
0.373 245
Gnutella (08)
0.276 591
Sister cities
0.607 783
Wikipedia talk (cy)
0.945 995
Wikipedia talk (oc)
0.597 879
Pretty Good Privacy
0.716 478
Gnutella (09)
0.225 136
Political blogs
0.603 600
Wikipedia talk (br)
0.822 255
OpenFlights (Opsahl)
0.652 641
Gnutella (06)
0.172 952
Gnutella (05)
0.122 850
US airports
0.723 066
Twitter lists
0.335 034
CiaoDVD trust
0.790 358
Infectious
0.084 991 9
Gnutella (04)
0.080 574 4
Hypertext 2009
0.005 997 03
Haggle
0.827 927
Chicago
0.098 109 0
LiquidFeedback (all)
0.527 836
Google+ (NIPS)
0.109 267
LiquidFeedback (temporal)
0.527 836
Autonomous systems (DIMACS10)
0.236 971
CAIDA
0.190 767
Bitcoin Alpha
0.516 941
Gnutella (25)
0.148 457
Advogato
0.603 415
Wikipedia talk (nds)
0.810 433
OpenFlights (Patokallio)
0.656 663
Gnutella (24)
0.026 316 2
Filmtipset friendships
0.063 112 0
Wikipedia talk (eo)
0.753 769
Gnutella (30)
0.166 035
Bitcoin OTC
0.481 386
Cora
0.416 988
Wikipedia links (gag)
0.521 379
Wikipedia links (lo)
0.954 815
DBLP
0.331 103
Wikipedia links (am)
0.463 072
Wikipedia links (mi)
0.634 850
Wikipedia links (so)
0.867 866
Astrophysics
0.663 931
Wikipedia links (vls)
0.728 583
JUNG/Javax
0.042 822 8
UC Irvine messages
0.130 119
Wikipedia talk (eu)
0.785 650
Condensed matter (2003)
0.607 353
Wikipedia links (bat-smg)
0.041 069 0
Wikipedia talk (gl)
0.726 009
Wikipedia links (nds-nl)
0.635 182
Java Development Kit
0.031 173 4
Wikipedia links (myv)
0.754 657
Wikipedia links (gv)
0.727 602
Wikipedia links (tk)
0.743 530
FOLDOC
0.152 740
Reactome
0.553 695
Chess
0.652 749
Wikipedia links (csb)
0.064 980 4
Wikipedia talk (lv)
0.902 004
Wikipedia links (crh)
0.720 867
Wikipedia links (wa)
0.399 425
Gnutella (31)
0.120 738
Wikipedia links (co)
0.880 880
Wikipedia links (gan)
0.758 292
Manufacturing emails
0.109 389
Wikipedia links (nah)
0.467 966
Wikipedia links (rue)
0.855 023
Google.com internal
0.165 743
Wikipedia links (lez)
0.776 768
Wikipedia links (dv)
0.942 372
Condensed matter (2005)
0.641 674
Wikipedia links (as)
0.769 644
arXiv astro-ph
0.700 817
Wikipedia links (si)
0.538 388
Wikipedia links (kv)
0.811 965
Digg
0.338 291
Wikipedia links (xal)
0.911 064
Wikipedia links (pam)
0.734 804
Linux sources
0.055 152 9
Wikipedia links (mhr)
0.365 320
Brightkite
0.650 823
Wikipedia links (fiu-vro)
0.937 193
Wikipedia elections
0.593 127
Wikipedia links (se)
0.713 534
Wikipedia talk (bn)
0.795 504
Wikipedia links (fo)
0.824 365
Wikipedia links (hsb)
0.189 187
Wikispeedia
0.281 762
Wikipedia links (os)
0.824 048
Wikipedia talk (sk)
0.939 699
Wikipedia links (hif)
0.889 858
Wikipedia links (diq)
0.892 740
Wikipedia links (vec)
0.423 768
Wikipedia links (cdo)
0.794 734
Wikipedia links (glk)
0.435 022
Wikipedia links (kn)
0.214 923
Slashdot
0.247 550
Wikipedia links (sah)
0.914 085
Wikipedia links (map-bms)
0.379 700
Wikipedia links (bcl)
0.921 608
Wikipedia links (gd)
0.657 630
arXiv hep-th
0.391 840
Wikipedia links (bh)
0.193 599
Edinburgh Associative Thesaurus
0.542 479
Internet topology
0.586 838
Wikipedia links (li)
0.669 298
Wikipedia links (xmf)
0.590 141
Douban
0.395 394
Wikipedia talk (el)
0.314 832
Wikipedia links (hak)
0.841 957
Wikipedia links (ht)
0.007 489 10
Wikipedia links (nso)
0.798 693
arXiv hep-ph
0.502 827
EU institution
0.425 255
Wikipedia links (mn)
0.897 887
Wikipedia links (arz)
0.799 376
Wikipedia links (or)
0.786 863
Epinions
0.723 602
Wikipedia links (pa)
0.613 617
Wikipedia links (nds)
0.281 807
Wikipedia links (ps)
0.688 812
Catster households
0.092 113 5
Wikipedia links (pms)
0.010 514 8
Wikipedia talk (sr)
0.529 573
Wikipedia links (yi)
0.029 119 8
Slashdot Zoo
0.594 523
SAP forums
0.172 382
Wikipedia links (bar)
0.024 890 4
Wikipedia talk (ca)
0.487 061
WordNet
0.114 963
Wikipedia links (als)
0.315 358
Wikipedia links (io)
0.512 175
Wikipedia links (ku)
0.754 806
Wikipedia links (min)
0.000 305 371
Wikipedia links (vo)
0.004 784 22
Wikipedia links (cv)
0.558 831
New York City
0.086 135 1
Wikipedia links (ky)
0.008 535 95
WikiSigned
0.481 211
Wikipedia links (nap)
0.810 002
San Francisco Bay Area
0.056 520 1
Wikipedia links (roa-tara)
0.761 273
Gowalla
0.283 628
Wikipedia links (yo)
0.833 494
Twitter (ICWSM)
0.046 055 0
MathOverflow
0.994 978
Wikipedia links (fy)
0.377 683
Wikipedia links (ckb)
0.852 318
Amazon (MDS)
0.031 835 0
Wikipedia links (sw)
0.506 031
Wikipedia links (is)
0.736 526
Wikipedia links (my)
0.589 048
Wikipedia links (su)
0.596 796
Wikipedia links (qu)
0.590 889
Wikipedia links (ba)
0.547 334
Wikipedia talk (sv)
0.827 077
Wikipedia links (ilo)
0.858 460
DBLP co-authorship
0.856 921
Colorado
0.031 638 7
Wikipedia talk (vi)
0.551 289
Wikipedia links (an)
0.145 635
Wikipedia links (mzn)
0.814 000
Wikipedia links (lb)
0.588 495
Wikipedia links (gu)
0.270 755
Wikipedia links (pnb)
0.688 527
Wikipedia links (sco)
0.607 506
Amazon (TWEB, 0302)
0.185 757
Wikipedia links (eml)
0.965 490
Wikipedia links (br)
0.496 177
Wikipedia links (zh-yue)
0.766 130
Epinions
0.755 904
Notre Dame
0.667 646
Wikipedia links (mr)
0.851 083
Wikipedia links (new)
0.333 550
Wikipedia links (jv)
0.203 570
Reality Mining
0.563 644
Pennsylvania
0.111 397
Facebook
0.011 597 7
CiteSeer
0.286 994
Wikipedia links (ia)
0.940 934
Wikipedia links (ast)
0.025 191 3
Linux kernel mailing list replies
0.745 741
Wikipedia talk (ja)
0.827 669
Wikipedia links (ml)
0.568 782
Flickr
0.829 008
Wikipedia links (bpy)
0.557 032
Enron (clean)
0.622 351
Enron
0.622 292
Wikipedia links (tl)
0.453 802
Livemocha
0.202 804
Texas
0.194 545
Stanford
0.048 796 6
Dogster households
0.454 941
Wikipedia links (sq)
0.560 155
Wikipedia links (be-x-old)
0.403 226
Wikipedia talk (pl)
0.027 970 6
Wikipedia links (ne)
0.917 945
Wikipedia links (bn)
0.780 787
Wikipedia links (te)
0.555 779
Wikipedia links (cy)
0.547 647
Catster/dogster households
0.092 113 5
Super User
0.984 410
Italian CNR
0.026 725 7
Yahoo advertisers
0.000 393 239
Baidu related
0.000 992 180
Florida
0.044 432 2
Youtube friendships
0.161 013
arXiv hep-th
0.896 403
Northwest USA
0.065 255 6
Wikipedia dynamic (simple)
0.260 291
Hyves
0.001 090 33
California
0.152 274
Wikipedia links (lmo)
0.642 381
Amazon (TWEB, 0312)
0.066 845 6
Wikipedia links (lv)
0.726 951
Wikipedia links (nn)
0.382 822
Wikipedia links (la)
0.034 253 1
Digg friends
0.602 264
Wikipedia links (sa)
0.899 878
Amazon (TWEB, 0505)
0.086 984 5
Amazon (TWEB, 0601)
0.081 961 5
Wikipedia talk (ar)
0.742 158
Wikipedia links (uz)
0.079 501 2
Wikipedia talk (ru)
0.926 913
Wikipedia links (az)
0.399 616
Wikipedia links (zh-min-nan)
0.445 746
Wikipedia talk (pt)
0.746 785
Catster
0.135 295
Wikipedia threads (de)
0.785 514
Northeast USA
0.091 415 7
Wikipedia links (tt)
0.567 452
Wikipedia talk (zh)
0.352 994
Wikipedia links (mk)
0.347 315
Wikipedia links (ka)
0.447 908
Wikipedia links (simple)
0.851 060
Wikipedia talk (es)
0.761 780
Wikipedia links (et)
0.768 870
Wikipedia messages (en)
0.354 761
Wikipedia links (bug)
0.967 553
Wikipedia links (tg)
0.744 885
Google hyperlinks
0.174 111
Youtube links
0.153 139
California and Nevada
0.087 808 9
Catster friends
0.134 819
Wikipedia links (el)
0.353 120
Wikipedia talk (it)
0.712 796
Wikipedia links (th)
0.741 684
Wikipedia links (lt)
0.439 082
Wikipedia links (be)
0.130 196
Wikipedia links (gl)
0.579 019
Prosper loans
0.046 288 4
arXiv hep-ph
0.862 128
Wikipedia links (ur)
0.690 935
Wikipedia links (ce)
0.357 110
Wikipedia links (hr)
0.709 841
Wikipedia links (sk)
0.058 417 5
Wikipedia links (ta)
0.782 805
Wikipedia links (hi)
0.285 823
Berkeley/Stanford
0.058 559 0
Dogster
0.353 261
Wikipedia links (sl)
0.720 574
Great Lakes
0.126 633
Wikipedia talk (fr)
0.977 206
Flixster
0.332 584
Wikipedia links (eu)
0.360 709
Dogster friends
0.351 696
TREC WT10g
0.043 241 4
Arnetminer ACM
0.029 684 4
Wikipedia links (bg)
0.584 039
Wikipedia conflict
0.260 217
Wikipedia links (da)
0.270 029
Eastern USA
0.091 415 7
Wikipedia links (eo)
0.504 167
Wikipedia links (bs)
0.685 612
Skitter
0.030 448 1
Wikipedia talk (de)
0.342 587
Higgs
0.169 817
Wikipedia links (kk)
0.604 716
Wikipedia links (he)
0.070 760 2
Catster/dogster friends
0.134 819
Wikipedia links (tr)
0.350 942
Wikipedia links (fi)
0.734 908
Flickr links
0.674 071
Indian domain
0.362 953
Hudong internal
0.467 526
DBpedia
0.005 699 68
Catster/Dogster
0.147 442
European Union domain
0.018 208 5
Baidu internal
0.090 247 1
Western USA
0.093 651 9
Wikipedia links (cs)
0.378 374
US patents
0.013 644 5
YouTube
0.082 089 1
Wikipedia links (hy)
0.150 866
Wikipedia links (no)
0.623 733
Wikipedia links (oc)
0.602 293
Libimseti.cz
0.167 400
Hudong related
0.016 316 5
Twitter mentions
0.002 874 42
Wikipedia links (ms)
0.687 501
Wikipedia links (ko)
0.809 878
Pokec
0.049 025 9
Wikipedia links (ro)
0.374 174
Wikipedia links (id)
0.898 809
Actor collaborations
0.867 127
Wikipedia links (war)
0.003 760 50
Wikipedia links (ca)
0.520 060
Wikipedia dynamic (nl)
0.259 531
Central USA
0.125 732
Wikipedia talk (en)
0.829 994
Wikipedia links (hu)
0.562 991
Wikipedia links (es)
0.022 150 4
Wikipedia dynamic (pl)
0.356 903
Wikipedia links (vi)
0.006 818 67
LiveJournal links
0.602 491
DBLP
0.347 088
Wikipedia links (pt)
0.561 257
Wikipedia links (uk)
0.347 736
Wikipedia links (nl)
0.006 990 40
Flickr
0.705 937
Wikipedia links (ar)
0.802 915
Wikipedia dynamic (it)
0.171 205
Wikipedia links (fa)
0.790 825
Wikipedia links (pl)
0.662 035
Full USA
0.125 732
Wikipedia links (zh)
0.491 122
Zhishi
0.002 588 92
LiveJournal
0.703 558
Wikipedia links (ceb)
0.002 288 73
Wikipedia growth (en)
0.240 561
Wikipedia links (ja)
0.553 512
Wikipedia links (ru)
0.264 277
Wikipedia links (de)
0.393 820
Wikipedia links (sh)
0.447 929
Wikipedia links (it)
0.291 943
Wikipedia links (sv)
0.003 068 33
Wikipedia dynamic (fr)
0.219 874
Stack Overflow
0.998 689
Orkut
0.388 622
Wikipedia links (fr)
0.186 485
Wikipedia links (sr)
0.068 941 3
Wikipedia dynamic (de)
0.386 372
DBpedia links
0.003 246 71
UK domain (2002)
0.141 624
Wikipedia links (en)
0.397 307
Google+ (IMC12)
0.509 053
Twitter (WWW)
0.319 460
Twitter (MPI)
0.380 728