1887
banner image
No data available.
Please log in to see this content.
You have no subscription access to this content.
No metrics data to plot.
The attempt to load metrics for this article has failed.
The attempt to plot a graph for these metrics has failed.
The full text of this article is not currently available.
f
Robust detection of dynamic community structure in networks
Rent:
Rent this article for
Access full text Article
/content/aip/journal/chaos/23/1/10.1063/1.4790830
1.
1. M. E. J. Newman, Networks: An Introduction (Oxford University Press, 2010).
2.
2. P. Holme and J. Saramäki, Phys. Rep. 519, 97 (2012).
http://dx.doi.org/10.1016/j.physrep.2012.03.001
3.
3. P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J.-P. Onnela, Science 328, 876 (2010).
http://dx.doi.org/10.1126/science.1184819
4.
4. D. S. Bassett, N. F. Wymbs, M. A. Porter, P. J. Mucha, J. M. Carlson, and S. T. Grafton, Proc. Natl. Acad. Sci. U.S.A. 108, 7641 (2011).
http://dx.doi.org/10.1073/pnas.1018985108
5.
5. J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A. L. Barabási, Proc. Natl. Acad. Sci. U.S.A. 104, 7332 (2007).
http://dx.doi.org/10.1073/pnas.0610245104
6.
6. Y. Wu, C. Zhou, J. Xiao, J. Kurths, and H. J. Schellnhuber, Proc. Natl. Acad. Sci. U.S.A. 107, 18803 (2010).
http://dx.doi.org/10.1073/pnas.1013140107
7.
7. S. Gonzaález-Bailón, J. Borge-Holthoefer, A. Rivero, and Y. Moreno, Sci. Rep. 1, 197 (2011).
http://dx.doi.org/10.1038/srep00197
8.
8. T. J. Fararo and J. Skvoretz, in Status, Network, and Structure: Theory Development in Group Processes (Stanford University Press, 1997), pp. 362386.
9.
9. A. Stomakhin, M. B. Short, and A. L. Bertozzi, Inverse Probl. 27, 115013 (2011).
http://dx.doi.org/10.1088/0266-5611/27/11/115013
10.
10. P. J. Mucha and M. A. Porter, Chaos 20, 041108 (2010).
http://dx.doi.org/10.1063/1.3518696
11.
11. A. S. Waugh, L. Pei, J. H. Fowler, P. J. Mucha, and M. A. Porter, “ Party polarization in Congress: A network science approach,” arXiv:0907.3509 (2011).
12.
12. K. W. Doron, D. S. Bassett, and M. S. Gazzaniga, Proc. Natl. Acad. Sci. U.S.A. 109, 18661 (2012).
http://dx.doi.org/10.1073/pnas.1216402109
13.
13. N. F. Wymbs, D. S. Bassett, P. J. Mucha, M. A. Porter, and S. T. Grafton, Neuron 74, 936 (2012).
http://dx.doi.org/10.1016/j.neuron.2012.03.038
14.
14. D. J. Fenn, M. A. Porter, M. McDonald, S. Williams, N. F. Johnson, and N. S. Jones, Chaos 19, 033119 (2009).
http://dx.doi.org/10.1063/1.3184538
15.
15. D. J. Fenn, M. A. Porter, S. Williams, M. McDonald, N. F. Johnson, and N. S. Jones, Phys. Rev. E 84, 026109 (2011).
http://dx.doi.org/10.1103/PhysRevE.84.026109
16.
16. M. A. Porter, J.-P. Onnela, and P. J. Mucha, Not. Am. Math. Soc. 56, 1082 (2009).
17.
17. H. Simon, Proc. Am. Philos. Soc. 106, 467 (1962).
18.
18. M. A. Porter, P. J. Mucha, M. Newman, and C. M. Warmbrand, Proc. Natl. Acad. Sci. U.S.A. 102, 7057 (2005).
http://dx.doi.org/10.1073/pnas.0500191102
19.
19. A. C. F. Lewis, N. S. Jones, M. A. Porter, and C. M. Deane, BMC Syst. Biol. 4, 100 (2010).
http://dx.doi.org/10.1186/1752-0509-4-100
20.
20. S. Fortunato, Phys. Rep. 486, 75 (2010).
http://dx.doi.org/10.1016/j.physrep.2009.11.002
21.
21. M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
http://dx.doi.org/10.1103/PhysRevE.69.026113
22.
22. A. Lancichinetti, F. Radicchi, and J. J. Ramasco, Phys. Rev. E 81, 046110 (2010).
http://dx.doi.org/10.1103/PhysRevE.81.046110
23.
23. M. E. J. Newman, Nat. Phys. 8, 25 (2012).
http://dx.doi.org/10.1038/nphys2162
24.
24. B. H. Good, Y. A. de Montjoye, and A. Clauset, Phys. Rev. E 81, 046106 (2010).
http://dx.doi.org/10.1103/PhysRevE.81.046106
25.
25. S. Fortunato and M. Barthélemy, Proc. Natl. Acad. Sci. U.S.A. 104, 36 (2007).
http://dx.doi.org/10.1073/pnas.0605965104
26.
26. P. J. Bickel and A. Chen, Proc. Natl. Acad. Sci. U.S.A. 106, 21068 (2009).
http://dx.doi.org/10.1073/pnas.0907096106
27.
27. S. Hutchings, “ The behavior of modularity-optimizing community detection algorithms,” M.Sc. Thesis (University of Oxford, 2011).
28.
28. M. E. J. Newman, Phys. Rev. E 69, 066133 (2004).
http://dx.doi.org/10.1103/PhysRevE.69.066133
29.
29. M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 103, 8577 (2006).
http://dx.doi.org/10.1073/pnas.0601602103
30.
30. J. Reichardt and S. Bornholdt, Phys. Rev. E 74, 016110 (2006).
http://dx.doi.org/10.1103/PhysRevE.74.016110
31.
31. J.-P. Onnela, D. J. Fenn, S. Reid, M. A. Porter, P. J. Mucha, M. D. Fricker, and N. S. Jones, Phys. Rev. E. 86, 036104 (2012).
http://dx.doi.org/10.1103/PhysRevE.86.036104
32.
32. U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner, IEEE Trans. Knowl. Data Eng. 20, 172 (2008).
http://dx.doi.org/10.1109/TKDE.2007.190689
33.
33. M. E. J. Newman, Phys. Rev. E 74, 036104 (2006).
http://dx.doi.org/10.1103/PhysRevE.74.036104
34.
34. T. Richardson, P. J. Mucha, and M. A. Porter, Phys. Rev. E 80, 036111 (2009).
http://dx.doi.org/10.1103/PhysRevE.80.036111
35.
35. G. Palla, A. Barabási, and T. Vicsek, Nature 446, 664 (2007).
http://dx.doi.org/10.1038/nature05670
36.
36.Equation (4) gives the definition for the notion of stationarity that we used in Ref. 4. The equation for this quantity in Ref. 4 has a typo in the denominator. We wrote incorrectly in that paper that the denominator was , whereas the numerical computations in that paper used .
37.
37.In other areas of investigation, it probably should be.
38.
38. E. T. Bullmore and D. S. Bassett, Ann. Rev. Clin. Psych. 7, 113 (2011).
http://dx.doi.org/10.1146/annurev-clinpsy-040510-143934
39.
39. D. S. Bassett, J. A. Brown, V. Deshpande, J. M. Carlson, and S. T. Grafton, Neuroimage 54, 1262 (2011).
http://dx.doi.org/10.1016/j.neuroimage.2010.09.006
40.
40. A. Zalesky, A. Fornito, I. H. Harding, L. Cocchi, M. Yucel, C. Pantelis, and E. T. Bullmore, Neuroimage 50, 970 (2010).
http://dx.doi.org/10.1016/j.neuroimage.2009.12.027
41.
41. J. Wang, L. Wang, Y. Zang, H. Yang, H. Tang, Q. Gong, Z. Chen, C. Zhu, and Y. He, Hum. Brain Mapp 30, 1511 (2009).
http://dx.doi.org/10.1002/hbm.20623
42.
42. S. Bialonski, M. T. Horstmann, and K. Lehnertz, Chaos 20, 013134 (2010).
http://dx.doi.org/10.1063/1.3360561
43.
43. A. A. Ioannides, Curr. Opin. Neurobiol. 17, 161 (2007).
http://dx.doi.org/10.1016/j.conb.2007.03.008
44.
44. C. T. Butts, Science 325, 414 (2009).
http://dx.doi.org/10.1126/science.1171022
45.
45. G. Kossinets, Soc. Networks 28, 247 (2006).
http://dx.doi.org/10.1016/j.socnet.2005.07.002
46.
46. A. Clauset, C. Moore, and M. E. J. Newman, Nature 453, 98 (2008).
http://dx.doi.org/10.1038/nature06830
47.
47. R. Guimerá and M. Sales-Pardo, Proc. Natl. Acad. Sci. U.S.A. 106, 22073 (2009).
http://dx.doi.org/10.1073/pnas.0908366106
48.
48. M. Kim and J. Leskovec, SIAM International Conference on Data Mining (2011).
49.
49. O. Sporns, Networks of the Brain (MIT, 2010).
50.
50. E. Bullmore and O. Sporns, Nat. Rev. Neurosci. 10, 186 (2009).
http://dx.doi.org/10.1038/nrn2575
51.
51. D. M. Abrams and S. H. Strogatz, Phys. Rev. Lett. 93, 174102 (2004).
http://dx.doi.org/10.1103/PhysRevLett.93.174102
52.
52. Y. Kuramoto and D. Battogtokh, Nonlinear Phenom. Complex Syst. 5, 380 (2002).
53.
53. S. I. Shima and Y. Kuramoto, Phys. Rev. E 69, 036213 (2004).
http://dx.doi.org/10.1103/PhysRevE.69.036213
54.
54. K. J. Friston, Hum. Brain Mapp 2, 56 (1994).
http://dx.doi.org/10.1002/hbm.460020107
55.
55. Y. Benjamini and Y. Yekutieli, Ann. Stat. 29, 1165 (2001).
http://dx.doi.org/10.1214/aos/1013699998
56.
56. E. Bullmore and O. Sporns, Nat. Rev. Neurosci. 13, 336 (2012).
http://dx.doi.org/10.1038/nrn3214
57.
57. V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, J. Stat. Mech. 10, P10008 (2008).
58.
58. I. S. Jutla, L. G. S. Jeub, and P. J. Mucha, “ A generalized Louvain method for community detection implemented in matlab,” (2011–2012); http://netwiki.amath.unc.edu/GenLouvain.
59.
59.A discrete time series can be represented as a vector. A continuous time series would first need to be discretized.
60.
60. D. Prichard and J. Theiler, Phys. Rev. Lett. 73, 951 (1994).
http://dx.doi.org/10.1103/PhysRevLett.73.951
61.
61.The code used for this computation actually operates on . However, this should be an equivalent mathematical estimate to the same computation on , which is the same except for a set of measure zero.
62.
62. H. Nakatani, I. Khalilov, P. Gong, and C. van Leeuwen, Phys. Lett. A 319, 167 (2003).
http://dx.doi.org/10.1016/j.physleta.2003.09.082
63.
63. A. Zalesky, A. Fornito, and E. Bullmore, Neuroimage 60, 2096 (2012).
http://dx.doi.org/10.1016/j.neuroimage.2012.02.001
64.
64. J. Theiler, S. Eubank, A. Longtin, B. Galdrikian, and J. D. Farmer, Physica D 58, 77 (1992).
http://dx.doi.org/10.1016/0167-2789(92)90102-S
65.
65.It is also important to note that the AAFT method can allow nonlinear correlations to remain in the surrogate data. Therefore, the development of alternative surrogate data generation methods might be necessary (Refs. 83 and 84).
66.
66.In the descriptions below, we use terms like “random” rewiring to refer to a process that we are applying uniformly at random aside from specified constraints.
67.
67. D. Garlaschelli, New J. Phys. 11, 073005 (2009).
http://dx.doi.org/10.1088/1367-2630/11/7/073005
68.
68. S. Maslov and K. Sneppen, Science 296, 910 (2002).
http://dx.doi.org/10.1126/science.1065103
69.
69. G. Ansmann and K. Lehnertz, Phys. Rev. E 84, 026103 (2011).
http://dx.doi.org/10.1103/PhysRevE.84.026103
70.
70. S. Bialonski, M. Wendler, and K. Lehnertz, PLoS ONE 6, e22826 (2011).
http://dx.doi.org/10.1371/journal.pone.0022826
71.
71. V. A. Traag, P. Van Dooren, and Y. Nesterov, Phys. Rev. E 84, 016114 (2011).
http://dx.doi.org/10.1103/PhysRevE.84.016114
72.
72. K. T. Macon, P. J. Mucha, and M. A. Porter, Physica A 391, 343 (2012).
http://dx.doi.org/10.1016/j.physa.2011.06.030
73.
73. A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, SIAM Rev. 53, 526 (2011).
http://dx.doi.org/10.1137/080734315
74.
74. D. S. Bassett, E. T. Owens, K. E. Daniels, and M. A. Porter, Phys. Rev. E 86, 041306 (2012).
http://dx.doi.org/10.1103/PhysRevE.86.041306
75.
75. X. Lou and J. A. Suykens, Chaos 21, 043116 (2011).
http://dx.doi.org/10.1063/1.3655371
76.
76. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, Phys. Rep. 469, 93 (2008).
http://dx.doi.org/10.1016/j.physrep.2008.09.002
77.
77. A. Arenas, A. Díaz-Guilera, and C. J. Pérez-Vicente, Phys. Rev. Lett. 96, 114102 (2006).
http://dx.doi.org/10.1103/PhysRevLett.96.114102
78.
78. J. Stout, M. Whiteway, E. Ott, M. Girvan, and T. M. Antonsen, Chaos 21, 025109 (2011).
http://dx.doi.org/10.1063/1.3581168
79.
79. G. Barlev, T. M. Antonsen, and E. Ott, Chaos 21, 025103 (2011).
http://dx.doi.org/10.1063/1.3596711
80.
80. A. Arenas, A. Díaz-Guilera, and C. J. Pérez-Vicente, Physica D 224, 27 (2006).
http://dx.doi.org/10.1016/j.physd.2006.09.029
81.
81. A. Lancichinetti and S. Fortunato, Sci. Rep. 2, 336 (2012).
http://dx.doi.org/10.1038/srep00336
82.
82. A. L. Traud, C. Frost, P. J. Mucha, and M. A. Porter, Chaos 19, 041104 (2009).
http://dx.doi.org/10.1063/1.3194108
83.
83. C. Räth, M. Gliozzi, I. E. Papadakis, and W. Brinkmann, Phys. Rev. Lett. 109, 144101 (2012).
http://dx.doi.org/10.1103/PhysRevLett.109.144101
84.
84. G. Rossmanith, H. Modest, C. Räth, A. J. Banday, K. M. Gorski, and G. Morfill, Phys. Rev. D 86, 083005 (2012).
http://dx.doi.org/10.1103/PhysRevD.86.083005
http://aip.metastore.ingenta.com/content/aip/journal/chaos/23/1/10.1063/1.4790830
Loading
/content/aip/journal/chaos/23/1/10.1063/1.4790830
Loading

Data & Media loading...

Loading

Article metrics loading...

/content/aip/journal/chaos/23/1/10.1063/1.4790830
2013-03-18
2014-10-22

Abstract

We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations (“optimization variance”) and over randomizations of network structure (“randomization variance”). Because the modularity quality function typically has a large number of nearly degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.

Loading

Full text loading...

/deliver/fulltext/aip/journal/chaos/23/1/1.4790830.html;jsessionid=376839wd5r1wd.x-aip-live-06?itemId=/content/aip/journal/chaos/23/1/10.1063/1.4790830&mimeType=html&fmt=ahah&containerItemId=content/aip/journal/chaos
true
true
This is a required field
Please enter a valid email address
752b84549af89a08dbdd7fdb8b9568b5 journal.articlezxybnytfddd
Scitation: Robust detection of dynamic community structure in networks
http://aip.metastore.ingenta.com/content/aip/journal/chaos/23/1/10.1063/1.4790830
10.1063/1.4790830
SEARCH_EXPAND_ITEM