# 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 ]

 Name Attributes bN 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