A Mathematical Analysis of Network Controllability Through Driver Nodes

被引：5
作者：
Chin S.P. [1 ,2 ]
Cohen J. [3 ]
Albin A. [3 ]
Hayvanovych M. [3 ]
Reilly E. [3 ]
Brown G. [1 ]
Harer J. [1 ]
机构：
[1] Department of Computer Science, Boston University, Boston, 02215, MA
[2] Systems and Technology Research, Woburn, 01801, MA
[3] Johns Hopkins University Applied Physics Laboratory, Laurel, 20723, MD
来源：
IEEE Transactions on Computational Social Systems | 2017年 / 4卷 / 02期
关键词：
Controllability; maximal matching; social network;
D O I：
10.1109/TCSS.2017.2698725
中图分类号：
学科分类号：
摘要：
A May 2011 Nature article by Liu, Slotine, and Barabasi laid a mathematical foundation for analyzing network controllability of self-organizing networks and how to identify the minimum number of nodes needed to control a network, or driver nodes. In this paper, we continue to explore this topic, beginning with a look at how Laplacian eigenvalues relate to the percentage of nodes required to control a network. Next, we define and analyze super driver nodes, or those driver nodes that survive graph randomization. Finally, we examine node properties to differentiate super driver nodes from other types of nodes in a graph. © 2014 IEEE.
引用
收藏
页码：40 / 51
页数：11
相关论文
共 19 条
  • [1] Chung F., Laplacians and the Cheeger inequality for directed graphs, Ann. Combinatorics, 9, 1, pp. 1-19, (2005)
  • [2] Chung F., Tsiatas A., Xu W., Dirichlet PageRank and trust-based ranking algorithms, Algorithms and Models for the Web Graph, 6732, pp. 103-114, (2011)
  • [3] Cowan N.J., Chastain E.J., Vilhena D.A., Freudenberg J.S., Bergstrom C.T., Nodal Dynamics, Not Degree Distributions, Determine the Structural Controllability of Complex Networks, (2011)
  • [4] Dulmage A.L., Mendelsohn N.S., Coverings of bipartite graphs, Can. J. Math, 10, 4, pp. 517-534, (1958)
  • [5] Hall P., On representatives of subsets, J. London Math. Soc, S1-10, 1, pp. 26-30, (1935)
  • [6] Hanhijarvi S., Garriga G.C., Puolamaki K., Randomization techniques for graphs, Proc. 9th SIAM Int. Conf. Data Mining (SDM), pp. 780-791, (2009)
  • [7] Jia T., Liu Y.-Y., Csoka E., Posfai M., Slotine J.-J., Barabasi A.-L., Emergence of bimodality in controlling complex networks, Nature Commun, 4, (2013)
  • [8] Johns J., Mahadevan S., Constructing basis functions from directed graphs for value function approximation, Proc. 24th Int. Conf. Mach. Learn, pp. 385-392, (2007)
  • [9] Kalman R.E., Mathematical description of linear dynamical systems, J. Soc. Ind. Appl. Math. A Control, 1, 2, pp. 152-192, (1963)
  • [10] Leskovec J., Slashdot Social Network, February 2009, (2009)
12