Controllability and modularity of complex networks. (English) Zbl 1395.90050
Summary: Two primary properties of complex networks, controllability and modularity not only are closely related to each other, but also play an important role in understanding the networks’ characteristics. In this paper, we discuss an elastic model to enhance the control of undirected networks and study the controllability of random networks with built-in gradually varied modularity as well as real-world networks to elaborate the correlation between the networks’ controllability and modularity. The results show that it is easier to control the networks with stronger modularity than that of weaker modularity, and the networks with larger size communities probably need more driver nodes to control than that of smaller size communities when we fix both the number of nodes and the number of links of the networks. In addition, the robustness analysis indicates that the model enhances the resistance of networks against link failure. This work shows that the controllability of complex networks is highly associated with the networks’ degree distribution as well as the networks’ modularity, which gives a new insight into the understanding of controllability and modularity of complex networks.
MSC:
| 90B10 | Deterministic network models in operations research |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Software:
GraphBaseReferences:
| [1] | Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 47-97 (2002) · Zbl 1205.82086 |
| [2] | Chen, L.; Yu, Q.; Chen, B., Anti-modularity and anti-community detecting in complex networks, Inf. Sci., 275, 293-313 (2014) · Zbl 1341.05234 |
| [3] | Danon, L.; Duch, J.; Diaz-Guilera, A., Comparing community structure identification, J. Stat. Mech.: Theory Exp., 09, P09008 (2005) |
| [4] | Erdős, P.; Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., 5, 17-61 (1960) · Zbl 0103.16301 |
| [5] | Fortunato, S., Community detection in graphs, Phys. Rep., 486, 75-174 (2010) |
| [6] | Fortunato, S.; Latora, V.; Marchiori, M., Method to find community structures based on information centrality, Phys. Rev. E, 70, 056104 (2004) |
| [7] | Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci., 99, 7821-7826 (2002) · Zbl 1032.91716 |
| [8] | Knuth, D. E., The Stanford GraphBase: A Platform for Combinatorial Computing (1993), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0806.68121 |
| [9] | Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Phys. Rev. E, 78, 046110 (2008) |
| [10] | Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., 54, 396-405 (2003) |
| [11] | Liu, Y. Y.; Slotine, J. J.; Barabási, A. L., Controllability of complex networks, Nature, 473, 167-173 (2011) |
| [12] | Newman, M. E.J., Detecting community structure in networks, Eur. Phys. J. B, 3, 8321-8330 (2004) |
| [13] | Newman, M. E.J., Modularity and community structure in networks, Proc. Natl. Acad. Sci., 103, 8577-8582 (2006) |
| [14] | Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 026113 (2003) |
| [15] | Nacher, J. C.; Akutsu, T., Dominating scale-free networks with variable scaling exponent: Heterogeneous networks are not difficult to control, New J. Phys., 14, 073005 (2012) |
| [16] | Nacher, J. C.; Akutsu, T., Structural controllability of unidirectional bipartite networks, Sci. Rep., 3, 1647 (2013) |
| [17] | Nacher, J. C.; Akutsu, T., Analysis of critical and redundant nodes in controlling directed and undirected complex networks using dominating sets, J. Complex Netw., 2, 394-412 (2014) · Zbl 1397.05179 |
| [18] | Nacher, J. C.; Akutsu, T., Structurally robust control of complex networks, Phys. Rev. E, 91, 012826 (2015) |
| [19] | Orman, G. K.; Labatut, V.; Cherifi, H., Comparative evaluation of community detection algorithms: a topological approach, J. Stat. Mech.: Theory Exp., 08, P08001 (2012) |
| [20] | Palla, G.; Derenyi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814-818 (2005) |
| [21] | Rosvall, M.; Bergstrom, C. T., An information-theoretic framework for resolving community structure in complex networks, Proc. Natl. Acad. Sci., 104, 7327-7331 (2007) |
| [22] | Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; Parisi, D., Defining and identifying communities in networks, Proc. Natl. Acad. Sci., 101, 2658-2663 (2004) |
| [23] | Reichardt, J.; Bornholdt, S., Statistical mechanics of community detection, Phys. Rev. E, 74, 016110 (2006) |
| [24] | Rubenstein, M.; Cornejo, A.; Nagpal, R., Programmable self-assembly in a thousand-robot swarm, Science, 345, 795-799 (2014) |
| [25] | Strogatz, S. H., Exploring complex networks, Nature, 410, 268-276 (2001) · Zbl 1370.90052 |
| [26] | Shang, Y.; Bouffanais, R., Influence of the number of topologically interacting neighbors on swarm dynamics, Sci. Rep., 4, 4184 (2014) |
| [27] | Sun, P. G.; Gao, L.; Yang, Y., Maximizing modularity intensity for community partition and evolution, Inf. Sci., 236, 82-93 (2013) |
| [28] | Sun, P. G.; Gao, L.; Han, S., Identification of overlapping and non-overlapping community structure by fuzzy clustering, Inf. Sci., 181, 1060-1071 (2011) · Zbl 1208.91120 |
| [29] | Sun, P. G., Methods to find community based on edge centrality, Physica A, 9, 1977-1988 (2013) |
| [30] | Sun, P. G., Weighting links based on edge centrality for community detection, Physica A, 394, 346-357 (2014) |
| [31] | Tan, Y.; Zheng, Z., Research advances in swarm robotics, Def. Technol., 9, 18-39 (2013) |
| [32] | Wuchty, S., Controllability in protein interaction networks, Proc. Natl. Acad. Sci., 11, 7156-7160 (2014) |
| [33] | Wang, W.-X.; Ni, X.; Lai, Y.-C.; Grebogi, C., Optimizing controllability of complex networks by small structural perturbations, Phys. Rev. E, 85, 026115 (2012) |
| [34] | Yang, Y.; Sun, P. G.; Hu, X.; Li, Z. J., Closed walks for community detection, Physica A, 397, 129-143 (2014) |
| [35] | Yuan, Z.; Zhao, C.; Di, Z.; Wang, W.-X.; Lai, Y.-C., Exact controllability of complex networks, Nat. Commun., 4, 1-9 (2013) |
| [36] | Yan, G.; Ren, J.; Lai, Y.-C.; Lai, C. H.; Li, B., Controlling complex networks - how much energy is needed, Phys. Rev. Lett., 108, 218703 (2012) |
| [37] | Zachary, W. W., An information flow model for conflict and fission in small groups, J. Anthropological Res., 33, 452-473 (1977) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
