Computer Science ›› 2019, Vol. 46 ›› Issue (10): 116-121.doi: 10.11896/jsjkx.180901759

• Network & Communication • Previous Articles     Next Articles

Information Diffusion Path Inferring Algorithm Based on Communication Data

XIANG Ying-zhuo, WEI Qiang, YOU Ling   

  1. (National Key Laboratory of Science and Technology on Blind Signal Processing,Chengdu 610041,China)
  • Received:2018-09-17 Revised:2018-12-12 Online:2019-10-15 Published:2019-10-21

Abstract: Information diffusion and propagation play an important role in viral marketing and virus diffusion.How-ever,in many occasions only the connected data of users in the network can be obtained,which makes it difficult to obtain the content of communication between users.To deal with such challenges,this paper proposed an information diffusion model based on probability in order to predict the relativity of communications between users,and then infer the diffusion path of information in the network.In addition,this paper proved that the complexity of solving the model is NP-hard,and proposed PathMine algorithm to get a near optimal solution.Experiment results show that the proposed PathMine algorithm outperforms other state-of-art algorithms.

Key words: Information diffusion, Information flow, Network analysis, Submodule function

CLC Number: 

  • TP311
[1]LAZARSFELD P F,KATZ E,ROPER E.Personal influence:The part played by people in the flow of mass communications[M].New York:Routledge,2017.
[2]ROGERS E M.Diffusion of innovations[M].Simon and Schuster,2010.
[3]WATTS D J,DODDS P S.Influentials,networks,and public opinion formation[J].Journal of Consumer Research,2007,34(4):441-458.
[4]MCCALLUM A,WANG X,CORRADA-EMMANUEL A. Topic and role discovery in social networks with experiments on enron and academic email[J].Journal of Artificial Intelligence Research,2007,30:249-272.
[5]ZHANG Y,WU Y,YANG Q.Community Discovery in Twitter Based on User Interests[J].Journal of Computational Information Systems,2012,8(3):991-1000.
[6]FEI H,JIANG R,YANG Y,et al.Content based social behavior prediction:a multi-task learning approach[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.ACM,2011:995-1000.
[7]LIN C,MEI Q,JIANG Y,et al.Inferring the diffusion and evolution of topics in social communities[C]//11th IEEE International Conference on Data Mining(ICDM 2011).Vancouver:IEEE,2011.
[8]ZHU J,XIONG F,PIAO D,et al.Statistically modeling the effectiveness of disaster information in social media[C]//Global Humanitarian Technology Conference (GHTC).IEEE,2011:431-436.
[9]ALTENBURGER,KRISTEN M,JOHAN U.Monophily in social networks introduces similarity among friends-of-friends[J].Nature Human Behaviour,2018,2(4):284.
[10]YANG M,HSU W H,KALLUMADI S T.Predictive Analytics of Social Networks:A Survey of Tasks and Techniques[J].Journal of Applied Physics,2014,112(1):014301-014301-5.
[11]ALBERT-LÁSZLÓ B.The origin of bursts and heavy tails in human dynamics[J].Nature,2005,435(7039):207.
[12]MALMGRENR D,STOUFFER D B,MOTTER A E,et al.A Poissonian explanation for heavy tails in e-mail communication[J].Proceedings of the National Academy of Sciences,2008,105(47):18153-18158.
[13]LESKOVEC J,MCGLOHON M,FALOUTSOS C,et al.Cascading behavior in large blog graphs: Patterns and a model.arXiv:0704.2803.
[14]KHULLER S,MOSS A,NAOR J.The budgeted maximum co-verage problem[J].Information Processing Letters,1991,70(1):39-45.
[15]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2007:420-429.
[16]GOYAL A,BONCHI F,LAKSHMANAN L V S.Learning influence probabilities in social networks[C]//Proceedings of the third ACM International Conference on Web Search and Data Mining.ACM,2010:241-250.
[17]LESKOVEC J,FALOUTSOS C.Scalable modeling of real graphs using kronecker multiplication[C]//Proceedings of the 24th International Conference on Machine Learning.ACM,2007:497-504.
[18]ERDS P,RÉNYI A.On the evolution of random graphs[J]. Transactions of the American Mathematical Society,2011,286(1):257-274.
[19]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98.
[20]GROVER A,ZWEIG A,ERMON S.Graphite:Iterative generative modeling of graphs[J].arXiv:1803.10459,2018.
[21]SHETTY J,ADIBI J.The Enron email dataset database schema and brief statistical report[R].Information Sciences Institute Technical Report,University of Southern California,2004:120-128.
[22]COHEN W W.Enron Email Data Set[OL].http://www.cs.cmu.edu/~enron/.
[1] TAN Qi, ZHANG Feng-li, ZHANG Zhi-yang, CHEN Xue-qin. Modeling Methods of Social Network User Influence [J]. Computer Science, 2021, 48(2): 76-86.
[2] LIU Ming-cong, WANG Na, ZHOU Ning. Dependency Analysis Based Cloud Composition Service Information Flow Control Mechanism [J]. Computer Science, 2019, 46(4): 189-196.
[3] WANG Xue-jian, ZHAO Guo-lei, CHANG Chao-wen, WANG Rui-yun. Illegal Flow Analysis for Lattice Model of Information Flow [J]. Computer Science, 2019, 46(2): 139-144.
[4] ZHU Hao,CHEN Jian-ping. Review of Trust Declassification for Software System [J]. Computer Science, 2018, 45(6A): 36-40.
[5] YAN Jia-qi, CHEN Jun-hua, LENG Jing. Total Communication and Efficiency Analysis of Large Scale Networks [J]. Computer Science, 2018, 45(6A): 283-289.
[6] HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network [J]. Computer Science, 2018, 45(6): 32-35.
[7] FAN Yan-fang. Temporal-Spatial-based Mandatory Access Control Model in Collaborative Environment [J]. Computer Science, 2017, 44(8): 107-114.
[8] WANG Zhen-fei, ZHU Jing-yang, ZHENG Zhi-yun and SONG Yu. Analysis of Microblog Community Users’ Influence Based on R-C Model [J]. Computer Science, 2017, 44(3): 254-258.
[9] DU Yuan-zhi, DU Xue-hui and YANG Zhi. Mixed Flow Policy Based On-demand Distributed Cloud Information Flow Control Model [J]. Computer Science, 2017, 44(10): 150-158.
[10] YANG Ying-hui, LI Jian-hua, NAN Ming-li, CUI Qiong and WANG Hong. Networked Operational Information Flowing Dynamic Hypergraph Model Based on Motif [J]. Computer Science, 2016, 43(8): 30-35.
[11] XIE Yang-xiao-jie and ZHAO Ling. Precise Identification of Seed Users Based on Information Flow in Big Data [J]. Computer Science, 2016, 43(7): 281-284.
[12] YANG Ying-hui, LI Jian-hua, NAN Ming-li and TIAN Yan-tao. Operational Architecture Modeling Based on Information Flow [J]. Computer Science, 2016, 43(2): 13-18.
[13] JIN Li and ZHU Hao. Declassification Policy Based on Automaton Monitoring [J]. Computer Science, 2015, 42(7): 194-199.
[14] SHAO Jing, CHEN Zuo-ning, YIN Hong-wu and XU Guo-chun. Design and Implementation of Information Flow Control Framework for PaaS [J]. Computer Science, 2015, 42(12): 257-262.
[15] JIN Li and ZHU Hao. Two-dimension Declassification Policy in Multithreaded Environments [J]. Computer Science, 2015, 42(12): 243-246.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!