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 312 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.

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
Train bombing
0.655 074
Sheep
0.755 225
Gene fusion
0.000 835 519
Les Misérables
0.561 283
Bison
0.790 714
David Copperfield
0.420 969
Windsurfers
0.724 591
Political books
0.564 121
Seventh graders
0.736 441
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
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
Wikipedia links (lo)
0.954 828
Wikipedia links (myv)
0.794 134
Cora
0.416 988
Wikipedia links (gag)
0.521 041
Wikipedia links (am)
0.461 409
DBLP
0.331 103
Wikipedia links (mi)
0.638 320
Wikipedia links (so)
0.868 118
Wikipedia links (vls)
0.725 324
Astrophysics
0.663 931
JUNG/Javax
0.042 822 8
UC Irvine messages
0.130 119
Wikipedia talk (eu)
0.785 650
Wikipedia links (bat-smg)
0.036 520 9
Condensed matter (2003)
0.607 353
Wikipedia talk (gl)
0.726 009
Wikipedia links (crh)
0.735 352
Wikipedia links (nds-nl)
0.640 818
Java Development Kit
0.031 173 4
Wikipedia links (tk)
0.743 681
FOLDOC
0.152 740
Reactome
0.553 695
Chess
0.652 749
Wikipedia links (csb)
0.064 979 9
Wikipedia talk (lv)
0.902 004
Wikipedia links (wa)
0.399 114
Wikipedia links (co)
0.881 802
Gnutella (31)
0.120 738
Wikipedia links (rue)
0.857 070
Wikipedia links (gan)
0.757 868
Manufacturing emails
0.109 389
Wikipedia links (nah)
0.468 934
Google.com internal
0.165 743
Wikipedia links (lez)
0.776 965
Wikipedia links (as)
0.610 185
Wikipedia links (si)
0.540 196
Wikipedia links (dv)
0.942 372
Condensed matter (2005)
0.641 674
arXiv astro-ph
0.700 817
Wikipedia links (kv)
0.813 068
Digg
0.338 291
Wikipedia links (xal)
0.965 375
Wikipedia links (pam)
0.734 886
Linux sources
0.055 152 9
Wikipedia links (mhr)
0.368 869
Brightkite
0.650 823
Wikipedia links (fiu-vro)
0.935 199
Wikipedia elections
0.593 127
Wikipedia links (ps)
0.867 492
Wikipedia links (se)
0.713 546
Wikipedia links (hsb)
0.185 079
Wikipedia links (fo)
0.824 313
Wikipedia links (os)
0.825 342
Wikipedia links (diq)
0.915 520
Wikipedia links (hif)
0.889 883
Wikipedia links (vec)
0.423 746
Wikipedia links (cdo)
0.794 461
Wikipedia links (kn)
0.225 748
Wikipedia links (glk)
0.436 545
Wikipedia links (sah)
0.914 088
Slashdot
0.247 550
Wikipedia links (gd)
0.656 169
Wikipedia links (map-bms)
0.379 734
Wikipedia links (bcl)
0.921 739
Wikipedia links (bh)
0.165 210
Wikipedia links (li)
0.678 193
arXiv hep-th
0.391 840
Edinburgh Associative Thesaurus
0.542 479
Internet topology
0.586 838
Wikipedia links (xmf)
0.590 072
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
Catster households
0.092 113 5
Wikipedia links (pms)
0.010 455 2
Wikipedia links (yi)
0.028 610 1
Slashdot Zoo
0.594 523
Wikipedia links (bar)
0.024 711 8
SAP forums
0.172 382
Wikipedia links (io)
0.505 786
Wikipedia links (als)
0.316 964
WordNet
0.114 963
Wikipedia links (ku)
0.753 329
Wikipedia links (min)
0.000 305 390
Wikipedia links (cv)
0.558 885
Wikipedia links (vo)
0.004 832 50
Wikipedia links (ky)
0.008 476 24
WikiSigned
0.481 211
Wikipedia links (ckb)
0.858 145
Wikipedia links (nap)
0.810 185
Wikipedia links (roa-tara)
0.761 028
Gowalla
0.283 628
Wikipedia links (yo)
0.833 499
Twitter (ICWSM)
0.046 055 0
Wikipedia links (fy)
0.378 236
Wikipedia links (sw)
0.506 020
Wikipedia links (is)
0.736 120
Amazon (MDS)
0.031 835 0
Wikipedia links (ba)
0.543 563
Wikipedia links (su)
0.631 121
Wikipedia links (my)
0.593 819
Wikipedia links (qu)
0.589 649
Wikipedia links (mg)
0.092 206 7
Wikipedia links (ilo)
0.858 507
Wikipedia links (scn)
0.862 899
DBLP co-authorship
0.856 921
Wikipedia links (ast)
0.025 191 3
Wikipedia links (an)
0.147 899
Wikipedia links (lb)
0.586 883
Wikipedia links (sco)
0.636 796
Wikipedia links (mzn)
0.814 375
Wikipedia links (gu)
0.269 533
Wikipedia links (eml)
0.966 967
Wikipedia links (pnb)
0.688 786
Facebook (WOSN)
0.629 659
Wikipedia links (ga)
0.708 498
Wikipedia links (br)
0.496 266
Wikipedia links (zh-yue)
0.774 754
Epinions
0.755 904
Wikipedia links (mr)
0.851 242
Notre Dame
0.667 646
Wikipedia links (af)
0.672 642
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 (ia)
0.943 858
Wikipedia links (ml)
0.568 782
Linux kernel mailing list replies
0.745 741
Flickr
0.829 008
Wikipedia links (bpy)
0.557 060
Enron (clean)
0.622 351
Enron
0.622 292
Texas
0.194 545
Stanford
0.048 796 6
Dogster households
0.454 941
Wikipedia talk (nl)
0.892 447
Catster/dogster households
0.092 113 5
Yahoo advertisers
0.000 393 239
Baidu related
0.000 992 180
Youtube friendships
0.161 013
arXiv hep-th
0.896 403
Wikipedia dynamic (simple)
0.260 291
California
0.152 274
Digg friends
0.602 264
Amazon (TWEB, 0601)
0.081 961 5
Wikipedia talk (ar)
0.742 158
Wikipedia talk (ru)
0.926 913
Wikipedia talk (pt)
0.746 785
Catster
0.135 295
Wikipedia talk (zh)
0.352 994
Wikipedia talk (es)
0.761 780
Wikipedia messages (en)
0.354 761
Google hyperlinks
0.174 111
Youtube links
0.153 139
Catster friends
0.134 819
Wikipedia talk (it)
0.712 796
Prosper loans
0.046 288 4
arXiv hep-ph
0.862 128
Berkeley/Stanford
0.058 559 0
Dogster
0.353 261
Wikipedia talk (fr)
0.977 206
Dogster friends
0.351 696
TREC WT10g
0.043 241 4
Wikipedia conflict
0.262 742
Skitter
0.030 448 1
Wikipedia talk (de)
0.342 587
Catster/dogster friends
0.134 819
Flickr links
0.674 062
Hudong internal
0.467 526
DBpedia
0.005 699 68
Catster/Dogster
0.147 442
Baidu internal
0.090 247 1
US patents
0.013 644 5
YouTube
0.082 089 1
Libimseti.cz
0.167 400
Hudong related
0.016 316 5
Twitter mentions
0.002 874 42
Pokec
0.049 025 9
Actor collaborations
0.867 127
Wikipedia dynamic (nl)
0.259 531
Wikipedia talk (en)
0.829 994
Wikipedia dynamic (pl)
0.356 903
LiveJournal links
0.602 491
Wikipedia links (pt)
0.562 801
DBLP
0.215 045
Flickr
0.705 937
Wikipedia dynamic (it)
0.171 205
Wikipedia links (pl)
0.422 287
Zhishi
0.002 588 92
LiveJournal
0.703 558
Wikipedia links (ja)
0.555 389
Wikipedia growth (en)
0.240 561
Wikipedia links (ru)
0.261 790
Wikipedia links (de)
0.432 720
Wikipedia links (it)
0.337 838
Wikipedia dynamic (fr)
0.219 874
Wikipedia links (fr)
0.099 090 1
Orkut
0.388 623
Wikipedia dynamic (de)
0.386 372
DBpedia links
0.003 246 71
Wikipedia links (en)
0.399 670
Google+ (IMC12)
0.509 053