Normalized non-bipartivity

These are the values of the normalized non-bipartivity (bN) for all networks to which the statistic applies and for which it was computed. In total, it has been computed for 227 networks.

The normalized non-bipartivity (bN) 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 normalized symmetric adjacency matrix N. It is defined as one plus the smallest eigenvalue. This is based on the property of the normalized adjacency matrix to have minimal eigenvalue minus one if and only if the graph is bipartite, or to be precise, when there is at least one bipartite connected component. However, in this computation only the largest connected component is taken into account. The value of one is an upper bound, but cannot be attained itself in a loopless graph; this can be seen by considering the trace of the normalized adjacency matrix, which is zero for loopless graphs.

The full definition of the normalized non-bipartivity as well as its properties and relationships to other graph statistics can be found in the KONECT handbook.

NameAttributesbN
HIV
0.004 033 53
Zachary karate club
0.285 389
Highland tribes
0.517 455
Taro exchange
0.318 664
Zebra
0.572 364
Kangaroos
0.654 378
Iceland
0.045 396 4
Contiguous USA
0.281 820
Rhesus macaques
0.625 357
Dolphins
0.286 231
Chesapeake Bay
0.352 276
Crisis in a Cloister
0.730 621
Cattle
0.671 382
PDZBase
0.002 569 68
Train bombing
0.454 523
Sheep
0.664 061
Gene fusion
0.006 500 11
Les Misérables
0.134 561
Bison
0.738 205
David Copperfield
0.276 497
Windsurfers
0.678 918
Political books
0.448 155
Seventh graders
0.702 142
Highschool
0.451 279
Hens
0.967 742
American football
0.557 894
Similarities (DBpedia)
0.067 790 0
Congress votes
0.237 671
Physicians
0.406 933
Japanese macaques
0.781 341
Euroroads
0.004 177 77
FilmTrust trust
0.033 988 3
Caenorhabditis elegans (metabolic)
0.200 551
Jazz musicians
0.460 437
Yeast
0.015 761 1
Little Rock Lake
0.184 147
LiquidFeedback (units)
0.006 504 81
Network science
0.255 201
Air traffic control
0.013 871 1
Residence hall
0.572 754
Facebook (NIPS)
0.001 554 35
A Song of Ice and Fire
0.123 682
LiquidFeedback (global)
0.003 524 84
Wikipedia talk (ht)
0.044 942 6
Caenorhabditis elegans
0.200 552
Hamsterster households
0.119 673
Caenorhabditis elegans (neural)
0.451 282
U. Rovira i Virgili
0.235 829
Florida ecosystem wet
0.446 582
Florida ecosystem dry
0.445 053
Dutch college
0.666 392
Human proteins (Stelzl)
0.011 883 7
Human proteins (Vidal)
0.060 887 7
Human proteins (Figeys)
0.050 174 8
US power grid
0.008 259 16
Bible
0.403 984
Hamsterster friendships
0.017 586 7
Hamsterster friends
0.017 586 7
Route views
0.045 798 5
DNC co-recipients
0.274 849
Hamsterster full
0.129 659
Adolescent health
0.216 902
Blogs
0.281 318
LiquidFeedback (issues)
0.066 744 8
LiquidFeedback (areas)
0.054 582 8
Gnutella (08)
0.040 345 9
Sister cities
0.006 720 90
Wikipedia talk (cy)
0.039 743 4
Wikipedia talk (oc)
0.055 316 2
Pretty Good Privacy
0.009 900 92
Gnutella (09)
0.035 143 9
OpenFlights (Opsahl)
0.030 222 1
US airports
0.160 504
Twitter lists
0.002 550 68
Infectious
0.364 710
Hypertext 2009
0.764 945
Haggle
0.466 542
Google+ (NIPS)
0.005 820 67
CAIDA
0.011 209 8
Filmtipset friendships
0.026 814 6
Wikipedia links (lo)
0.042 131 7
Wikipedia links (myv)
0.184 322
Cora
0.017 591 2
Wikipedia links (gag)
0.141 210
Wikipedia links (am)
0.015 123 9
Wikipedia links (mi)
0.083 642 4
Wikipedia links (so)
0.001 330 02
Wikipedia links (vls)
0.112 524
JUNG/Javax
0.162 291
UC Irvine messages
0.132 355
Wikipedia links (bat-smg)
0.048 975 7
Wikipedia links (crh)
0.041 941 8
Wikipedia links (nds-nl)
0.129 764
Java Development Kit
0.160 371
Wikipedia links (gv)
0.179 420
Wikipedia links (tk)
0.049 848 7
Wikipedia links (csb)
0.037 241 1
Wikipedia links (wa)
0.079 907 0
Wikipedia links (co)
0.006 997 60
Gnutella (31)
0.059 887 0
Wikipedia links (rue)
0.102 014
Wikipedia links (gan)
0.024 953 0
Manufacturing emails
0.286 679
Wikipedia links (nah)
0.048 643 0
Google.com internal
0.004 475 19
Wikipedia links (lez)
0.096 450 2
Wikipedia links (as)
0.006 861 04
Wikipedia links (si)
0.005 562 69
Wikipedia links (dv)
0.020 031 2
Condensed matter (2005)
0.050 332 4
arXiv astro-ph
0.084 055 4
Wikipedia links (kv)
0.031 120 2
Digg
0.037 413 4
Wikipedia links (xal)
0.010 127 0
Wikipedia links (pam)
0.032 870 9
Wikipedia links (mhr)
0.075 984 7
Brightkite
0.015 484 9
Wikipedia links (fiu-vro)
0.064 821 6
Wikipedia links (ps)
0.033 511 9
Wikipedia links (se)
0.028 803 9
Wikipedia links (hsb)
0.044 764 8
Wikipedia links (fo)
0.080 340 0
Wikipedia links (os)
0.105 747
Wikipedia links (diq)
0.035 709 7
Wikipedia links (hif)
0.028 095 8
Wikipedia links (vec)
0.070 440 5
Wikipedia links (cdo)
1.371 52 × 10−5
Wikipedia links (kn)
0.046 968 0
Wikipedia links (glk)
0.019 190 9
Wikipedia links (sah)
0.053 967 7
Slashdot
0.014 353 1
Wikipedia links (gd)
0.055 711 7
Wikipedia links (map-bms)
0.039 433 2
Wikipedia links (bcl)
0.040 989 9
Wikipedia links (bh)
0.004 667 11
Wikipedia links (li)
0.003 336 55
arXiv hep-th
0.036 274 2
Edinburgh Associative Thesaurus
0.482 007
Internet topology
0.016 724 9
Wikipedia links (xmf)
0.053 509 8
Wikipedia links (hak)
0.066 904 4
Wikipedia links (ht)
0.010 305 6
Wikipedia links (nso)
0.073 494 1
arXiv hep-ph
0.057 397 4
EU institution
9.817 48 × 10−5
Wikipedia links (mn)
0.020 972 7
Wikipedia links (arz)
0.055 767 4
Wikipedia links (or)
0.066 537 4
Wikipedia links (pa)
0.030 880 1
Wikipedia links (nds)
0.034 412 0
Wikipedia links (pms)
0.043 413 5
Wikipedia links (yi)
0.032 615 5
Slashdot Zoo
0.042 441 3
Wikipedia links (bar)
0.011 192 4
SAP forums
0.014 608 0
Wikipedia links (io)
0.060 257 6
Wikipedia links (als)
0.158 861
WordNet
0.046 198 2
Wikipedia links (ku)
0.057 876 5
Wikipedia links (min)
0.000 265 219
Wikipedia links (cv)
0.092 221 5
Wikipedia links (vo)
0.026 912 7
Wikipedia links (ky)
0.017 136 2
WikiSigned
0.011 578 8
Wikipedia links (ckb)
0.019 198 7
Wikipedia links (nap)
0.049 778 1
Wikipedia links (roa-tara)
0.116 968
Gowalla
0.017 892 4
Wikipedia links (yo)
0.007 084 91
Twitter (ICWSM)
0.003 658 47
Wikipedia links (fy)
0.062 091 7
Wikipedia links (sw)
0.072 293 5
Wikipedia links (is)
0.021 565 1
Wikipedia links (ba)
0.087 027 9
Wikipedia links (su)
0.002 190 65
Wikipedia links (my)
0.020 101 6
Wikipedia links (qu)
0.035 680 6
Wikipedia links (mg)
0.006 281 13
Wikipedia links (ilo)
0.147 012
Wikipedia links (scn)
0.022 801 9
Wikipedia links (ast)
0.090 543 9
Wikipedia links (an)
0.075 943 6
Wikipedia links (lb)
0.079 936 6
Wikipedia links (sco)
0.049 209 8
Wikipedia links (mzn)
0.061 124 0
Wikipedia links (gu)
0.086 220 4
Wikipedia links (eml)
0.210 502
Wikipedia links (pnb)
0.057 387 6
Facebook (WOSN)
0.031 728 7
Wikipedia links (ga)
0.102 155
Wikipedia links (br)
0.094 136 9
Wikipedia links (zh-yue)
0.036 668 6
Epinions
0.017 168 2
Wikipedia links (mr)
0.017 695 7
Notre Dame
4.997 07 × 10−5
Wikipedia links (af)
0.057 427 0
Wikipedia links (new)
0.003 264 43
Wikipedia links (jv)
0.023 353 8
Reality Mining
0.783 795
Pennsylvania
0.001 041 12
Facebook
0.029 854 5
CiteSeer
0.004 807 89
Wikipedia links (ia)
0.044 347 6
Wikipedia links (ml)
0.042 367 0
Flickr
0.066 857 3
Wikipedia links (bpy)
0.030 059 1
Enron
0.001 262 22
Texas
0.001 117 89
Stanford
0.000 583 688
Baidu related
0.000 756 745
arXiv hep-th
0.152 926
Wikipedia dynamic (simple)
0.024 180 5
California
0.000 418 791
Amazon (TWEB, 0601)
0.035 629 1
Catster
0.025 052 7
Wikipedia messages (en)
0.016 804 0
Google hyperlinks
0.001 246 93
Youtube links
0.002 045 96
arXiv hep-ph
0.232 408
Berkeley/Stanford
0.000 201 474
Dogster
0.040 102 7
TREC WT10g
0.000 182 942
Wikipedia conflict
0.074 904 1
Skitter
0.001 329 05
Hudong internal
0.000 913 442
DBpedia
0.000 311 520
Catster/Dogster
0.071 405 9