| 社会网络中影响集选择的一个近似算法 |
| |
| 引用本文： | 冀桂琳,黄晓晖.社会网络中影响集选择的一个近似算法[J].新疆大学学报(理工版),2014(3):304-306. |
| |
| 作者姓名： | 冀桂琳 黄晓晖 |
| |
| 作者单位： | 新疆大学数学与系统科学学院 |
| |
| 基金项目： | Supported by NSFC(61222201);SRFDP(20126501110001);Xinjiang talent project(2013711011) |
| |
| 摘 要： | 在研究社会网络影响集的选择问题中,目标是选取网络G中的一个最小点集S,使得V（G）-S中的每个点都至少有一半邻点在S中.本文给出一个α（△＋1）/δ＋1-近似算法,其中δ和△分别表示图G的最小度和最大度,α是局部独立数,它指示着图G的局部区域中最多含有的独立点的个数.
|
| 关 键 词： | 社会网络 影响集选择 近似算法 独立集 |
An Approximation Algorithm for the Influential Nodes Selection Problem in Social Network |
| |
| JI Gui-lin;HUANG Xiao-hui.An Approximation Algorithm for the Influential Nodes Selection Problem in Social Network[J].Journal of Xinjiang University(Science & Engineering),2014(3):304-306. |
| |
| Authors: | JI Gui-lin;HUANG Xiao-hui |
| |
| Institution: | JI Gui-lin;HUANG Xiao-hui;College of Mathematics and System Sciences, Xinjiang University; |
| |
| Abstract: | In this paper, we study the problem of selecting a minimum set S of influential nodes in a social network G such that every node in V（G）- S has at least half of its neighbors in S. An approximation algorithm is given with performance ratio αl（△ ＋ 1）/δ ＋ 1, where δ and △ are the minimum and the maximum degree of G, respectively, and αlis the local independence number indicating how many independent nodes can be distributed in a local area. |
| |
| Keywords: | Social network influential node selection approximation algorithm independent set |
| 本文献已被 CNKI 维普 等数据库收录！ |
