文章基本信息

标题：A Weighted Maximum Matching Algorithm for Influence Maximization and Structural Controllability 1 1 Supported by the International Design Centre (Grant IDG31300103).
本地全文：下载
作者：Giorgio Sartor ; Yeow Khiang Chia ; Laura Wynter 等
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2017
卷号：50
期号：1
页码：14447-14453
DOI：10.1016/j.ifacol.2017.08.2288
语种：English
出版社：Elsevier
摘要：AbstractStructural control and influence maximization on networks both admit the problem of selecting a particular subset of nodes. In structural control, the subset of nodes should guarantee the controllability of the network (in the usual sense) for almost any combination of weights. In influence maximization, given a diffusion process over the network, the chosen subset of nodes (of a given cardinality) should produce the greatest diffusive influence over the rest of the network. While structural control exploits only the structure of the network, influence maximization depends both on the structure and the weights of the edges. We modify an algorithm originally developed for structural control to take advantage of the weights as well, and we show it can be used to find competitive solutions to the influence maximization problem, while guaranteeing structural controllability. This also suggests an underlying similarity between these models, despite their intrinsic differences and the contexts in which they are usually used. We develop analytic results for two extreme cases, the binary tree and the two-level star graph, as well as empirical results for a selection of random graphs.
关键词：KeywordsStructural controllabilityInfluence maximizationNetworksControl placement