新疆大学学报（自然科学版）
新疆大學學報（自然科學版）
신강대학학보（자연과학판）
XINJIANG UNIVERSITY JOURNAL(NATURAL SCIENCE EDITION)
2014年
3期
304-306
,共3页
社会网络%影响集选择%近似算法%独立集
社會網絡%影響集選擇%近似算法%獨立集
사회망락%영향집선택%근사산법%독립집
Social network%influential node selection%approximation algorithm,independent set
在研究社会网络影响集的选择问题中，目标是选取网络G中的一个最小点集S ，使得V(G)-S 中的每个点都至少有一半邻点在S 中。本文给出一个α‘(?+1)/δ+1-近似算法，其中δ和?分别表示图G的最小度和最大度，α‘是局部独立数，它指示着图G的局部区域中最多含有的独立点的个数。
在研究社會網絡影響集的選擇問題中，目標是選取網絡G中的一箇最小點集S ，使得V(G)-S 中的每箇點都至少有一半鄰點在S 中。本文給齣一箇α‘(?+1)/δ+1-近似算法，其中δ和?分彆錶示圖G的最小度和最大度，α‘是跼部獨立數，它指示著圖G的跼部區域中最多含有的獨立點的箇數。
재연구사회망락영향집적선택문제중，목표시선취망락G중적일개최소점집S ，사득V(G)-S 중적매개점도지소유일반린점재S 중。본문급출일개α‘(?+1)/δ+1-근사산법，기중δ화?분별표시도G적최소도화최대도，α‘시국부독립수，타지시착도G적국부구역중최다함유적독립점적개수。
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αl is the local independence number indicating how many independent nodes can be distributed in a local area.
