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

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 ]

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
Pro League (2016/2017)
0.832 478
Train bombing
0.454 523
Sheep
0.664 061
Gene fusion
0.006 500 11
Les Misérables
0.134 561
Bundesliga (2016/2017)
0.825 038
Bison
0.738 205
David Copperfield
0.276 497
Windsurfers
0.678 918
Political books
0.448 155
Seventh graders
0.702 142
Ligue 1 (2016/2017)
0.846 165
Premier League (2013/2014)
0.818 136
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
Erdős
0.012 483 3
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
Political blogs
0.207 586
Wikipedia talk (br)
0.080 055 5
OpenFlights (Opsahl)
0.030 222 1
Gnutella (06)
0.120 710
Gnutella (05)
0.109 553
US airports
0.160 504
Twitter lists
0.002 550 68
CiaoDVD trust
0.062 702 3
Infectious
0.364 710
Gnutella (04)
0.021 890 1
Hypertext 2009
0.764 945
Haggle
0.466 542
Chicago
0.022 914 0
LiquidFeedback (all)
0.082 707 9
Google+ (NIPS)
0.005 820 67
LiquidFeedback (temporal)
0.082 707 9
Autonomous systems (DIMACS10)
0.036 705 4
CAIDA
0.011 209 8
Bitcoin Alpha
0.039 852 3
Gnutella (25)
0.028 354 6
Advogato
0.130 758
Wikipedia talk (nds)
0.007 856 82
OpenFlights (Patokallio)
0.032 163 5
Gnutella (24)
0.065 985 4
Filmtipset friendships
0.026 814 6
Wikipedia talk (eo)
0.056 411 3
Gnutella (30)
0.061 233 1
Bitcoin OTC
0.039 855 0
Cora
0.017 591 2
Wikipedia links (gag)
0.141 438
Wikipedia links (lo)
0.049 376 7
DBLP
0.047 487 4
Wikipedia links (am)
0.015 584 4
Wikipedia links (mi)
0.083 437 4
Wikipedia links (so)
0.067 751 8
Astrophysics
0.088 359 2
Wikipedia links (vls)
0.112 524
JUNG/Javax
0.162 291
UC Irvine messages
0.132 355
Wikipedia talk (eu)
0.003 538 48
Condensed matter (2003)
0.075 005 1
Wikipedia links (bat-smg)
0.048 976 7
Wikipedia talk (gl)
0.064 314 9
Wikipedia links (nds-nl)
0.129 765
Java Development Kit
0.160 371
Wikipedia links (myv)
0.183 788
Wikipedia links (gv)
0.179 420
Wikipedia links (tk)
0.046 335 5
FOLDOC
0.435 186
Reactome
0.027 970 9
Chess
0.051 195 9
Wikipedia links (csb)
0.037 299 8
Wikipedia talk (lv)
0.011 472 6
Wikipedia links (crh)
0.041 942 4
Wikipedia links (wa)
0.079 907 2
Gnutella (31)
0.059 887 0
Wikipedia links (co)
0.006 997 65
Wikipedia links (gan)
0.024 954 0
Manufacturing emails
0.286 679
Wikipedia links (nah)
0.048 566 1
Wikipedia links (rue)
0.097 076 7
Google.com internal
0.004 475 19
Wikipedia links (lez)
0.096 518 5
Wikipedia links (dv)
0.020 031 2
Condensed matter (2005)
0.050 332 4
Wikipedia links (as)
0.006 861 41
arXiv astro-ph
0.084 055 4
Wikipedia links (si)
0.005 562 72
Wikipedia links (kv)
0.031 121 2
Digg
0.037 413 4
Wikipedia links (xal)
0.010 124 6
Wikipedia links (pam)
0.032 885 3
Linux sources
0.017 431 8
Wikipedia links (mhr)
0.075 984 9
Brightkite
0.015 484 9
Wikipedia links (fiu-vro)
0.064 840 6
Wikipedia elections
0.100 581
Wikipedia links (se)
0.043 985 5
Wikipedia talk (bn)
0.011 150 6
Wikipedia links (fo)
0.080 340 1
Wikipedia links (hsb)
0.044 765 0
Wikispeedia
0.382 642
Wikipedia links (os)
0.105 750
Wikipedia talk (sk)
0.022 163 5
Wikipedia links (hif)
0.028 350 8
Wikipedia links (diq)
0.035 709 7
Wikipedia links (vec)
0.070 440 6
Wikipedia links (cdo)
1.371 52 × 10−5
Wikipedia links (glk)
0.019 199 8
Wikipedia links (kn)
0.033 430 3
Slashdot
0.014 353 1
Wikipedia links (sah)
0.021 206 7
Wikipedia links (map-bms)
0.039 431 9
Wikipedia links (bcl)
0.058 912 5
Wikipedia links (gd)
0.055 711 8
arXiv hep-th
0.036 274 2
Wikipedia links (bh)
0.018 429 7
Edinburgh Associative Thesaurus
0.482 007
Internet topology
0.016 724 9
Wikipedia links (li)
0.003 341 38
Wikipedia links (xmf)
0.053 511 8
Douban
0.009 618 19
Wikipedia talk (el)
0.021 515 7
Wikipedia links (hak)
0.067 154 8
Wikipedia links (ht)
0.010 883 2
Wikipedia links (nso)
0.073 494 8
arXiv hep-ph
0.057 397 4
EU institution
9.817 48 × 10−5
Wikipedia links (mn)
0.020 976 0
Wikipedia links (arz)
0.055 940 9
Wikipedia links (or)
0.066 534 9
Epinions
0.016 785 3
Wikipedia links (pa)
0.020 379 9
Wikipedia links (nds)
0.034 493 0
Wikipedia links (ps)
0.033 518 6
Catster households
0.048 055 4
Wikipedia links (pms)
0.043 992 6
Wikipedia talk (sr)
0.011 641 0
Wikipedia links (yi)
0.033 019 3
Slashdot Zoo
0.042 441 3
SAP forums
0.014 608 0
Wikipedia links (bar)
0.011 263 9
Wikipedia talk (ca)
0.036 461 6
WordNet
0.046 198 2
Wikipedia links (als)
0.158 865
Wikipedia links (io)
0.062 142 9
Wikipedia links (ku)
0.057 877 9
Wikipedia links (min)
0.000 267 588
Wikipedia links (vo)
0.026 913 2
Wikipedia links (cv)
0.095 808 8
New York City
0.000 780 111
Wikipedia links (ky)
0.019 009 4
WikiSigned
0.011 578 8
Wikipedia links (nap)
0.049 793 3
San Francisco Bay Area
0.000 214 122
Wikipedia links (roa-tara)
0.116 968
Gowalla
0.017 892 4
Wikipedia links (yo)
0.007 265 22
Twitter (ICWSM)
0.003 658 47
MathOverflow
0.132 313
Wikipedia links (fy)
0.062 094 0
Wikipedia links (ckb)
0.019 215 9
Amazon (MDS)
0.012 895 0
Wikipedia links (sw)
0.073 999 6
Wikipedia links (is)
0.021 755 8
Wikipedia links (mg)
0.006 299 97
Wikipedia links (my)
0.032 561 5
Wikipedia links (qu)
0.035 680 6
Wikipedia links (ba)
0.087 051 1
Wikipedia talk (sv)
0.042 919 5
Wikipedia links (ilo)
0.147 132
Wikipedia links (scn)
0.022 801 9
DBLP co-authorship
0.032 705 7
Colorado
0.000 187 031
Wikipedia talk (vi)
0.006 308 98
Wikipedia links (an)
0.075 946 9
Wikipedia links (mzn)
0.058 034 0
Wikipedia links (lb)
0.079 939 9
Wikipedia links (pnb)
0.057 390 7
Facebook (WOSN)
0.031 728 7
Wikipedia links (sco)
0.050 117 1
Amazon (TWEB, 0302)
0.038 117 4
Wikipedia links (eml)
0.210 516
Wikipedia links (ga)
0.131 511
Wikipedia links (br)
0.094 137 1
Wikipedia links (zh-yue)
0.036 670 9
Notre Dame
4.997 07 × 10−5
Wikipedia links (mr)
0.042 925 8
Wikipedia links (new)
0.003 264 67
Reality Mining
0.783 795
Pennsylvania
0.001 041 12
Facebook
0.029 854 5
CiteSeer
0.004 807 89
Wikipedia links (af)
0.057 430 8
Wikipedia links (ia)
0.073 662 1
Wikipedia links (ast)
0.123 448
Ask Ubuntu
0.027 748 7
Linux kernel mailing list replies
0.001 368 08
Wikipedia talk (ja)
0.027 208 6
Wikipedia links (ml)
0.043 935 7
Flickr
0.066 857 3
Wikipedia links (bpy)
0.030 386 6
Wikipedia links (tl)
0.004 198 98
Livemocha
0.104 296
Texas
0.001 117 89
Stanford
0.000 583 688
Dogster households
0.076 116 3
Wikipedia links (sq)
0.023 987 3
Wikipedia links (be-x-old)
0.131 628
Wikipedia links (ne)
0.004 153 65
Wikipedia links (bn)
0.004 066 65
Wikipedia links (te)
0.048 363 0
Wikipedia links (cy)
0.011 465 4
Wikipedia talk (nl)
0.020 941 1
Catster/dogster households
0.048 055 4
Super User
0.036 249 7
Italian CNR
0.000 102 737
Yahoo advertisers
0.058 508 8
Baidu related
0.000 756 745
Florida
0.000 176 070
Youtube friendships
0.002 045 96
arXiv hep-th
0.152 926
Northwest USA
0.000 148 562
Wikipedia dynamic (simple)
0.024 180 5
Hyves
0.020 659 5
California
0.000 418 791
Wikipedia links (lmo)
0.110 041
Amazon (TWEB, 0312)
0.036 611 5
Wikipedia links (lv)
0.088 088 9
Wikipedia links (nn)
0.035 211 4
Wikipedia links (la)
0.026 503 7
Digg friends
0.005 757 20
Wikipedia links (sa)
0.012 375 9
Amazon (TWEB, 0505)
0.030 406 0
Amazon (TWEB, 0601)
0.035 629 1
Wikipedia talk (ar)
0.008 921 28
Wikipedia links (uz)
0.004 560 58
Wikipedia talk (ru)
0.030 047 7
Wikipedia links (az)
0.088 493 3
Wikipedia links (zh-min-nan)
0.001 492 00
Wikipedia talk (pt)
0.014 708 2
Catster
0.025 052 7
Wikipedia threads (de)
0.043 517 8
Northeast USA
0.000 394 322
Wikipedia links (tt)
0.009 434 73
Wikipedia talk (zh)
0.012 765 2
Wikipedia links (mk)
0.038 918 1
Wikipedia links (ka)
0.066 220 7
Wikipedia links (simple)
0.052 780 8
Wikipedia talk (es)
0.017 255 3
Wikipedia links (et)
0.086 435 1
Wikipedia messages (en)
0.016 804 0
Wikipedia links (bug)
0.034 140 5
Wikipedia links (tg)
0.024 265 5
Google hyperlinks
0.001 246 93
Youtube links
0.002 045 96
California and Nevada
0.000 181 755
Catster friends
0.025 052 7
Wikipedia links (el)
0.062 379 6
Wikipedia talk (it)
0.029 882 2
Wikipedia links (th)
0.056 063 6
Wikipedia links (lt)
0.132 337
Wikipedia links (be)
0.085 817 2
Wikipedia links (gl)
0.239 960
Prosper loans
0.058 899 8
arXiv hep-ph
0.232 408
Wikipedia links (ur)
0.017 262 0
Wikipedia links (ce)
0.070 789 6
Wikipedia links (hr)
0.117 852
Wikipedia links (sk)
0.003 234 13
Wikipedia links (ta)
0.070 028 9
Wikipedia links (hi)
0.031 632 9
Berkeley/Stanford
0.000 201 474
Dogster
0.040 102 7
Wikipedia links (sl)
0.103 092
Great Lakes
7.028 07 × 10−5
Wikipedia talk (fr)
0.012 556 7
Flixster
0.010 436 1
Wikipedia links (eu)
0.022 929 7
Dogster friends
0.040 102 7
TREC WT10g
0.000 182 942
Arnetminer ACM
0.005 042 82
Wikipedia links (bg)
0.036 143 2
Wikipedia conflict
0.074 872 1
Wikipedia links (da)
0.077 462 7
Eastern USA
8.569 60 × 10−5
Wikipedia links (eo)
0.073 017 2
Wikipedia links (bs)
0.076 740 7
Skitter
0.001 329 05
Wikipedia talk (de)
0.018 009 7
Higgs
0.054 334 1
Wikipedia links (kk)
0.075 374 2
Wikipedia links (he)
0.048 940 2
Catster/dogster friends
0.025 052 7
Wikipedia links (tr)
0.048 021 7
Wikipedia links (fi)
0.090 137 0
Flickr links
0.001 850 47
Indian domain
4.113 59 × 10−5
Hudong internal
0.000 913 442
DBpedia
0.000 326 204
Catster/Dogster
0.071 405 9
European Union domain
8.978 75 × 10−5
Baidu internal
0.003 126 37
Western USA
6.231 10 × 10−5
Wikipedia links (cs)
0.072 688 2
US patents
0.008 306 86
YouTube
0.001 666 96
Wikipedia links (hy)
0.045 708 8
Wikipedia links (oc)
0.044 885 0
Libimseti.cz
0.133 489
Hudong related
0.000 427 231
Twitter mentions
0.000 598 655
Wikipedia links (ms)
0.012 128 2
Wikipedia links (ko)
0.027 254 3
Pokec
0.012 475 3
Wikipedia links (ro)
0.026 696 7
Wikipedia links (id)
0.003 989 22
Actor collaborations
0.153 139
Wikipedia links (war)
0.013 041 8
Wikipedia links (ca)
0.071 917 2
Wikipedia dynamic (nl)
0.018 706 0
Central USA
7.028 07 × 10−5
Wikipedia talk (en)
0.031 296 9
Wikipedia links (hu)
0.028 416 1
Wikipedia links (es)
0.008 366 30
Wikipedia dynamic (pl)
0.017 545 8
Wikipedia links (vi)
0.026 112 5
LiveJournal links
0.005 867 16
DBLP
0.024 538 3
Wikipedia links (pt)
0.039 453 6
Wikipedia links (uk)
0.036 479 8
Wikipedia links (nl)
0.027 370 9
Flickr
0.001 780 25
Wikipedia links (ar)
0.006 391 85
Wikipedia dynamic (it)
0.019 282 9
Wikipedia links (fa)
0.004 084 26
Wikipedia links (pl)
0.037 584 2
Full USA
6.231 10 × 10−5
Wikipedia links (zh)
0.031 713 3
Zhishi
0.001 534 53
LiveJournal
0.005 300 70
Wikipedia links (ceb)
0.028 738 6
Wikipedia growth (en)
0.021 029 4
Wikipedia links (ja)
0.050 930 5
Wikipedia links (ru)
0.012 519 1
Wikipedia links (de)
0.025 022 7
Wikipedia links (sh)
0.036 310 7
Wikipedia links (it)
0.086 823 0
Wikipedia links (sv)
0.028 943 5
Wikipedia dynamic (fr)
0.019 718 6
Stack Overflow
0.050 881 6
Orkut
0.113 924
Wikipedia links (fr)
0.036 999 4
Wikipedia links (sr)
0.012 427 3
Wikipedia dynamic (de)
0.022 280 9
DBpedia links
0.003 374 45
Wikipedia links (en)
0.018 197 8
Google+ (IMC12)
0.004 642 58