Efficient Algorithms towards Network Intervention
Efficient Algorithms towards Network Intervention
复制标题
DOI：
10.1145/3366423.3380269
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Hui-Ju Hung;Wang-Chien Lee;De-Nian Yang;Chih-Ya Shen;Zhen Lei;Sy-Miin Chow
中科院分区：
文献类型：
--
作者：
Hui-Ju Hung;Wang-Chien Lee;De-Nian Yang;Chih-Ya Shen;Zhen Lei;Sy-Miin Chow
研究表明，社会关系对个人的健康结果有重大影响。网络干预，通过仔细规划，可以帮助网络用户建立健康的关系。然而，大多数以前的工作并没有被设计为通过仔细检查和改进多个网络特性来帮助这种规划。在本文中，我们提出和评估算法，促进网络干预规划，通过同时优化网络度，接近度，介数，和局部聚类系数，涉及网络干预有限退化的情况下-单目标（NILD-S）和网络干预有限退化-多目标（NILD-M）。我们证明了NILD-S和NILD-M是NP-困难的，除非P=NP，否则不能在多项式时间内以任何比例近似。提出了NILD-S的保留相关性的候选重选（CRPD）算法和NILD-M的干扰感知边缘选择和调整（OISA）算法。为了提高算法的效率，设计了多种剪枝策略。通过在公立学校和Web上收集的各种真实的社交网络上的大量实验和实证研究，证明CRPD和OISA在效率和效果上都优于基线。
Research suggests that social relationships have substantial impacts on individuals’ health outcomes. Network intervention, through careful planning, can assist a network of users to build healthy relationships. However, most previous work is not designed to assist such planning by carefully examining and improving multiple network characteristics. In this paper, we propose and evaluate algorithms that facilitate network intervention planning through simultaneous optimization of network degree, closeness, betweenness, and local clustering coefficient, under scenarios involving Network Intervention with Limited Degradation - for Single target (NILD-S) and Network Intervention with Limited Degradation - for Multiple targets (NILD-M). We prove that NILD-S and NILD-M are NP-hard and cannot be approximated within any ratio in polynomial time unless P=NP. We propose the Candidate Re-selection with Preserved Dependency (CRPD) algorithm for NILD-S, and the Objective-aware Intervention edge Selection and Adjustment (OISA) algorithm for NILD-M. Various pruning strategies are designed to boost the efficiency of the proposed algorithms. Extensive experiments on various real social networks collected from public schools and Web and an empirical study are conducted to show that CRPD and OISA outperform the baselines in both efficiency and effectiveness.