冀桂琳, 黄晓晖. 社会网络中影响集选择的一个近似算法(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2014, 31(3): 304-306.DOI：
社会网络中影响集选择的一个近似算法(英文)
摘要
在研究社会网络影响集的选择问题中
目标是选取网络G中的一个最小点集S
使得V(G)-S中的每个点都至少有一半邻点在S中.本文给出一个α(△+1)/δ+1-近似算法
其中δ和△分别表示图G的最小度和最大度
α是局部独立数
它指示着图G的局部区域中最多含有的独立点的个数.
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
references
Domingos P,Richardson M.Mining the network value of customers[C].in KDD’01:proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining,New York,NY,USA:ACM,2001,57-66.
Richardson M,Domingos P.Mining knowledge-sharing sites for viral marketing[C].in KDD’02:proceding of the eighth ACM SIGKDD international conference on knowledge discovery and data mining,New York,NY,USA:ACM,2002,61-70.
Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence through a social network[C].in KDD’03:proceedings of the ninth ACM SIGKDD international conference on knownledge discovery and data mining,New York,NY,USA:ACM,2003,137-146.
Kempe D,Kleinberg J,Tardos E.Influential Nodes in a Diffusion Model for Social Networks[J].in ICALP,Springer-Verlag,2005,3380:1127-1138.
Mossel E,Roch S.Submodularity of infuence in social networks:from local to global[J].SIAM J Comput,2010,39:2176-2188.
Zou F,Zhang Z,Wu W L.Latency-bounded minimum influence node selection in social networks[J].in:proceedings of workshop on Social Networks,Applications,and Systems,Boston,2009,5682:519-526.
Zou F,Willson J K,Zhang Z,et al.Fast information propagation in social networks[J].Discrete Mathematics,Algorithms and Applications,2010,2:125-141.
Bondy JA,Murty USR.Graph theory with application[M].London:Macmillan,1976.
京公网安备11010802024621