School of Mathematics, Renmin University of China, Beijing, China.
School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian province, China.
PLoS One. 2020 Mar 12;15(3):e0229201. doi: 10.1371/journal.pone.0229201. eCollection 2020.
The dissemination of information on networks involves many important practical issues, such as the spread and containment of rumors in social networks, the spread of infectious diseases among the population, commercial propaganda and promotion, the expansion of political influence and so on. One of the most important problems is the influence-maximization problem which is to find out k most influential nodes under a certain propagate mechanism. Since the problem was proposed in 2001, many works have focused on maximizing the influence in a single network. It is a NP-hard problem and the state-of-art algorithm IMM proposed by Youze Tang et al. achieves a ratio of 63.2% of the optimum with nearly linear time complexity. In recent years, there have been some works of maximizing influence on multilayer networks, either in the situation of single or multiple influences. But most of them study seed selection strategies to maximize their own influence from the perspective of participants. In fact, the problem from the perspective of network owners is also worthy of attention. Since network participants have not had access to all information of the network for reasons such as privacy protection and corporate interests, they may have access to only part of the social network. The owners of networks can get the whole picture of the networks, and they need not only to maximize the overall influence, but also to consider allocating seeds to their customers fairly, i.e., the Fair Seed Allocation (FSA) problem. As far as we know, FSA problem has been studied on a single network, but not on multilayer networks yet. From the perspective of network owners, we propose a multiple-influence diffusion model MMIC on multilayer networks and its FSA problem. Two solutions of FSA problem are given in this paper, and we prove theoretically that our seed allocation schemes are greedy. Subsequent experiments also validate the effectiveness of our approaches.
网络信息的传播涉及到许多重要的实际问题，例如社交网络中的谣言传播和遏制、人群中的传染病传播、商业宣传和推广、政治影响力的扩大等。其中最重要的问题之一是影响最大化问题，即在给定传播机制下找出 k 个最具影响力的节点。自 2001 年提出该问题以来，许多工作都集中在最大化单个网络中的影响力。这是一个 NP 难问题，Youze Tang 等人提出的最先进算法 IMM 以近乎线性的时间复杂度实现了最优解的 63.2%的比例。近年来，已有一些关于多层网络上的最大影响力的工作，无论是在单影响还是多影响的情况下。但大多数都是从参与者的角度研究种子选择策略来最大化自身的影响力。事实上，从网络所有者的角度来看，这个问题也值得关注。由于隐私保护和企业利益等原因，网络参与者无法获得网络的所有信息，他们可能只能访问部分社交网络。网络所有者可以获得网络的全貌，他们不仅需要最大化整体影响力，还需要公平地为其客户分配种子，即公平种子分配（FSA）问题。据我们所知，FSA 问题已经在单网络上进行了研究，但尚未在多层网络上进行研究。从网络所有者的角度出发，我们在多层网络上提出了一个多影响扩散模型 MMIC 及其 FSA 问题。本文给出了 FSA 问题的两种解决方案，并从理论上证明了我们的种子分配方案是贪婪的。随后的实验也验证了我们方法的有效性。
