基于关键节点的影响力最大化算法
|
摘要
为解决LDAG(DAG Algorithm Based on Linear Threshold)算法在处理关于社会网络影响力最大化过程中,优先考虑网络影响力传播模型、忽视社会网络的拓扑结构问题,利用社交网络社区的结构,有针对性地选择影响力传播的关键节点,对LDAG算法进行了改进。利用关键节点简化了有向无环图的构造过程,保证了其高精度与运行效率高的特点,同时也优化了算法的时间复杂度和空间复杂度。通过两个有效的实验数据集对算法进行验证,结果表明改进的算法可以大幅度降低算法的运行时间,且对算法的精度影响很小。
LDAG( DAG algorithm based on linear threshold) algorithm is a heuristic algorithm for maximizing the influence of social networks. It has the characteristics of high accuracy and high efficiency. When solving the problem of maximizing the influence of social networks,the network influence propagation model is given priority,and then the topological structure of social networks is ignored. In this paper,the LDAG algorithm is improved by using the structure of social network community to select the key nodes of influence propagation.The key nodes are used to simplify the construction process of directed acyclic graph,optimize the time complexity and space complexity of the algorithm,and validate the rationality of the algorithm by using two effective experimental data sets.
LDAG( DAG algorithm based on linear threshold) algorithm is a heuristic algorithm for maximizing the influence of social networks. It has the characteristics of high accuracy and high efficiency. When solving the problem of maximizing the influence of social networks,the network influence propagation model is given priority,and then the topological structure of social networks is ignored. In this paper,the LDAG algorithm is improved by using the structure of social network community to select the key nodes of influence propagation.The key nodes are used to simplify the construction process of directed acyclic graph,optimize the time complexity and space complexity of the algorithm,and validate the rationality of the algorithm by using two effective experimental data sets.
引文
[1]SABRINA HELM.Viral Marketing-Establishing Customer Relationships by‘Word-of-Mouse’[J].Electronic Markets,2000,10(3):158-161.
[2]DOMINGOS P,RICHARDSON M.Mining the Network Value of Customers[C]∥Proceedings of the 7th ACM SIGKDDInternational Conference on Knowledge Discover and Data Mining.San Francisco,USA:ACM,2001:57-66.
[3]RICHARDSON M,DOMINGOS P.Mining Knowledge-Aharing Sites for Viral Marketing[C]∥Proceedings of the 8th ACMSIGKDD International Conference on Knowledge Discover and Data Mining.Edmonton,Canada:ACM,2002:61-70.
[4]KEMPE D,KLEINBERG J,TARDOS E.Maximizing the Spread of Influence through a Social Network[C]∥In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA:ACM,2003:137-146.
[5]KEMPE D,KLEINBERG J,VA TARDOS.Influential Nodes in a Diffusion Model for Social Networks[C]∥International Colloquium on Automata,Languages,and Programming.Berlin,Heidelberg:Springer,2005:1127-1138.
[6]CHEN Wei,WANG Y,YANG S.Efficient Influence Maximization in Social Networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris,France:ACM,2009:199-208.
[7]田家堂,王轶彤,冯小军.一种新型的社会网络影响最大化算法[J].计算机学报,2011,34(10):1956-1965.TIAN Jiatang,WANG Yitong,FENG Xiaojun.A New Social Network Effect Maximization Algorithm[J].Chinese Journal of Computers,2011,34(10):1956-1965.
[8]CHEN H,WANG Y.Threshold-Based Heuristic Algorithm for Influence Maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.
[9]CHEN Wei,WANG C,WANG Y.Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA:ACM,2010:1029-1038.
[10]李国良,楚娅萍,冯建华,等.多社交网络的影响力最大化分析[J].计算机学报,2016,39(4):643-656.LI Guoliang,CHU Yaping,FENG Jianhua,et al.Analysis of the Influence Maximization of Multiple Social Networks[J].Chinese Journal of Computers,2016,39(4):643-656.
[11]CHEN W,YUAN Y,ZHANG L.Scalable Influence Maximization in Social Networks under the Linear Threshold Model[C]∥KDD'10 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.USA,New York:ACM,2010:1029-1038.
[12]GOLDENBERG J,LIBAI B,MULLER E.Talk of the Network:A Complex Systems Look at the Underlying Process of Wordof-Mouth[J].Marketing Letters,2001,12(3):211-223.
[13]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast Unfolding of Communities in Large Networks[J].Journal of Statistical Mechanics,2008(10):155-168.
[14]NEWMAN M E,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Phys Rev E Stat Nonlin Soft Matter Phys,2004,69(2):026113.
[15]赵之滢,于海,朱志良,等.基于网络社团结构的节点传播影响力分析[J].计算机学报,2014(4):753-766.ZHAO Zhiying,YU Hai,ZHU Zhiliang,et al.Analysis of Influence of Node Communication Based on Network Community Structure[J]. Chinese Journal of Computers,2014(4):753-766.
[2]DOMINGOS P,RICHARDSON M.Mining the Network Value of Customers[C]∥Proceedings of the 7th ACM SIGKDDInternational Conference on Knowledge Discover and Data Mining.San Francisco,USA:ACM,2001:57-66.
[3]RICHARDSON M,DOMINGOS P.Mining Knowledge-Aharing Sites for Viral Marketing[C]∥Proceedings of the 8th ACMSIGKDD International Conference on Knowledge Discover and Data Mining.Edmonton,Canada:ACM,2002:61-70.
[4]KEMPE D,KLEINBERG J,TARDOS E.Maximizing the Spread of Influence through a Social Network[C]∥In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA:ACM,2003:137-146.
[5]KEMPE D,KLEINBERG J,VA TARDOS.Influential Nodes in a Diffusion Model for Social Networks[C]∥International Colloquium on Automata,Languages,and Programming.Berlin,Heidelberg:Springer,2005:1127-1138.
[6]CHEN Wei,WANG Y,YANG S.Efficient Influence Maximization in Social Networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris,France:ACM,2009:199-208.
[7]田家堂,王轶彤,冯小军.一种新型的社会网络影响最大化算法[J].计算机学报,2011,34(10):1956-1965.TIAN Jiatang,WANG Yitong,FENG Xiaojun.A New Social Network Effect Maximization Algorithm[J].Chinese Journal of Computers,2011,34(10):1956-1965.
[8]CHEN H,WANG Y.Threshold-Based Heuristic Algorithm for Influence Maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.
[9]CHEN Wei,WANG C,WANG Y.Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA:ACM,2010:1029-1038.
[10]李国良,楚娅萍,冯建华,等.多社交网络的影响力最大化分析[J].计算机学报,2016,39(4):643-656.LI Guoliang,CHU Yaping,FENG Jianhua,et al.Analysis of the Influence Maximization of Multiple Social Networks[J].Chinese Journal of Computers,2016,39(4):643-656.
[11]CHEN W,YUAN Y,ZHANG L.Scalable Influence Maximization in Social Networks under the Linear Threshold Model[C]∥KDD'10 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.USA,New York:ACM,2010:1029-1038.
[12]GOLDENBERG J,LIBAI B,MULLER E.Talk of the Network:A Complex Systems Look at the Underlying Process of Wordof-Mouth[J].Marketing Letters,2001,12(3):211-223.
[13]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast Unfolding of Communities in Large Networks[J].Journal of Statistical Mechanics,2008(10):155-168.
[14]NEWMAN M E,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Phys Rev E Stat Nonlin Soft Matter Phys,2004,69(2):026113.
[15]赵之滢,于海,朱志良,等.基于网络社团结构的节点传播影响力分析[J].计算机学报,2014(4):753-766.ZHAO Zhiying,YU Hai,ZHU Zhiliang,et al.Analysis of Influence of Node Communication Based on Network Community Structure[J]. Chinese Journal of Computers,2014(4):753-766.