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 400 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 (lo)
0.954 815
DBLP
0.331 103
Wikipedia links (am)
0.463 072
Astrophysics
0.663 931
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 talk (gl)
0.726 009
Java Development Kit
0.031 173 4
Wikipedia links (myv)
0.754 657
FOLDOC
0.152 740
Reactome
0.553 695
Chess
0.652 749
Wikipedia talk (lv)
0.902 004
Gnutella (31)
0.120 738
Manufacturing emails
0.109 389
Wikipedia links (rue)
0.855 023
Google.com internal
0.165 743
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
Digg
0.338 291
Wikipedia links (pam)
0.734 804
Linux sources
0.055 152 9
Wikipedia links (mhr)
0.365 320
Brightkite
0.650 823
Wikipedia elections
0.593 127
Wikipedia talk (bn)
0.795 504
Wikipedia links (hsb)
0.189 187
Wikispeedia
0.281 762
Wikipedia links (os)
0.824 048
Wikipedia talk (sk)
0.939 699
Wikipedia links (cdo)
0.794 734
Wikipedia links (kn)
0.214 923
Slashdot
0.247 550
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 072
Douban
0.395 394
Wikipedia talk (el)
0.314 832
Wikipedia links (hak)
0.841 993
Wikipedia links (ht)
0.007 403 12
Wikipedia links (nso)
0.798 779
arXiv hep-ph
0.502 827
EU institution
0.425 255
Wikipedia links (mn)
0.897 849
Wikipedia links (arz)
0.797 182
Wikipedia links (or)
0.817 599
Epinions
0.723 602
Wikipedia links (pa)
0.636 484
Wikipedia links (nds)
0.268 383
Wikipedia links (ps)
0.867 492
Catster households
0.092 113 5
Wikipedia links (pms)
0.010 455 2
Wikipedia talk (sr)
0.529 573
Wikipedia links (yi)
0.028 610 1
Slashdot Zoo
0.594 523
SAP forums
0.172 382
Wikipedia links (bar)
0.024 711 8
Wikipedia talk (ca)
0.487 061
WordNet
0.114 963
Wikipedia links (als)
0.316 964
Wikipedia links (io)
0.505 786
Wikipedia links (ku)
0.753 329
Wikipedia links (min)
0.000 305 390
Wikipedia links (vo)
0.004 832 50
Wikipedia links (cv)
0.558 885
New York City
0.086 135 1
Wikipedia links (ky)
0.008 476 24
WikiSigned
0.481 211
Wikipedia links (nap)
0.810 185
San Francisco Bay Area
0.056 520 1
Wikipedia links (roa-tara)
0.761 028
Gowalla
0.283 628
Wikipedia links (yo)
0.833 499
Twitter (ICWSM)
0.046 055 0
MathOverflow
0.994 978
Wikipedia links (fy)
0.378 236
Wikipedia links (ckb)
0.858 145
Amazon (MDS)
0.031 835 0
Wikipedia links (sw)
0.506 020
Wikipedia links (is)
0.736 120
Wikipedia links (mg)
0.092 206 7
Wikipedia links (my)
0.593 819
Wikipedia links (su)
0.631 121
Wikipedia links (qu)
0.589 649
Wikipedia links (ba)
0.543 563
Wikipedia talk (sv)
0.827 077
Wikipedia links (ilo)
0.858 507
Wikipedia links (scn)
0.862 899
DBLP co-authorship
0.856 921
Colorado
0.031 638 7
Wikipedia talk (vi)
0.551 289
Wikipedia links (an)
0.147 899
Wikipedia links (mzn)
0.814 375
Wikipedia links (lb)
0.586 883
Wikipedia links (gu)
0.269 533
Wikipedia links (pnb)
0.688 786
Facebook (WOSN)
0.629 659
Wikipedia links (sco)
0.636 796
Amazon (TWEB, 0302)
0.185 757
Wikipedia links (eml)
0.966 967
Wikipedia links (ga)
0.708 498
Wikipedia links (br)
0.496 266
Wikipedia links (zh-yue)
0.774 754
Epinions
0.755 904
Notre Dame
0.667 646
Wikipedia links (mr)
0.851 242
Wikipedia links (new)
0.333 550
Wikipedia links (jv)
0.188 484
Reality Mining
0.563 644
Pennsylvania
0.111 397
Facebook
0.011 597 7
CiteSeer
0.286 994
Wikipedia links (af)
0.672 642
Wikipedia links (ia)
0.943 858
Wikipedia links (ast)
0.025 191 3
Ask Ubuntu
0.992 928
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 060
Enron (clean)
0.622 351
Enron
0.622 292
Wikipedia links (tl)
0.455 725
Livemocha
0.202 804
Texas
0.194 545
Stanford
0.048 796 6
Dogster households
0.454 941
Wikipedia links (sq)
0.587 977
Wikipedia links (be-x-old)
0.426 604
Wikipedia talk (pl)
0.027 970 6
Wikipedia links (ne)
0.887 569
Wikipedia links (bn)
0.780 787
Wikipedia links (te)
0.555 779
Wikipedia links (cy)
0.547 647
Wikipedia talk (nl)
0.892 447
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.730 805
Wikipedia links (nn)
0.386 627
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.082 009 9
Wikipedia talk (ru)
0.926 913
Wikipedia links (az)
0.399 629
Wikipedia links (zh-min-nan)
0.449 944
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.568 810
Wikipedia talk (zh)
0.352 994
Wikipedia links (mk)
0.347 315
Wikipedia links (ka)
0.447 908
Wikipedia links (simple)
0.852 236
Wikipedia talk (es)
0.761 780
Wikipedia links (et)
0.748 042
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.399 649
Wikipedia talk (it)
0.712 796
Wikipedia links (th)
0.744 273
Wikipedia links (lt)
0.439 082
Wikipedia links (be)
0.116 073
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.025 838 7
Wikipedia links (hr)
0.709 841
Wikipedia links (sk)
0.058 334 0
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 800
Dogster friends
0.351 696
TREC WT10g
0.043 241 4
Arnetminer ACM
0.029 684 4
Wikipedia links (bg)
0.598 075
Wikipedia conflict
0.260 217
Wikipedia links (da)
0.270 029
Eastern USA
0.091 415 7
Wikipedia links (eo)
0.514 474
Wikipedia links (bs)
0.688 789
Skitter
0.030 448 1
Wikipedia talk (de)
0.342 587
Higgs
0.169 817
Wikipedia links (kk)
0.605 710
Wikipedia links (he)
0.070 760 2
Catster/dogster friends
0.134 819
Wikipedia links (tr)
0.336 919
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.149 988
Wikipedia links (no)
0.687 090
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.808 788
Pokec
0.049 025 9
Wikipedia links (ro)
0.395 220
Wikipedia links (id)
0.902 342
Actor collaborations
0.867 127
Wikipedia links (war)
0.003 640 48
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.021 127 8
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.404 311
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