CFP last date
20 June 2024
Reseach Article

A Survey on Finding Influential Individuals to Maximize Influences Spread within Social Network

Published on December 2014 by Shital T. Tupe, Samadhan Sonavane
Innovations and Trends in Computer and Communication Engineering
Foundation of Computer Science USA
ITCCE - Number 4
December 2014
Authors: Shital T. Tupe, Samadhan Sonavane
5596667c-624e-4465-88b8-9837e8bcfc4c

Shital T. Tupe, Samadhan Sonavane . A Survey on Finding Influential Individuals to Maximize Influences Spread within Social Network. Innovations and Trends in Computer and Communication Engineering. ITCCE, 4 (December 2014), 16-19.

@article{
author = { Shital T. Tupe, Samadhan Sonavane },
title = { A Survey on Finding Influential Individuals to Maximize Influences Spread within Social Network },
journal = { Innovations and Trends in Computer and Communication Engineering },
issue_date = { December 2014 },
volume = { ITCCE },
number = { 4 },
month = { December },
year = { 2014 },
issn = 0975-8887,
pages = { 16-19 },
numpages = 4,
url = { /proceedings/itcce/number4/19062-2028/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 Innovations and Trends in Computer and Communication Engineering
%A Shital T. Tupe
%A Samadhan Sonavane
%T A Survey on Finding Influential Individuals to Maximize Influences Spread within Social Network
%J Innovations and Trends in Computer and Communication Engineering
%@ 0975-8887
%V ITCCE
%N 4
%P 16-19
%D 2014
%I International Journal of Computer Applications
Abstract

Finding influential individuals is an important part in Social Networks. The main aim of influence maximization is to find the top influential individuals in a social network. Many basic greedy algorithms have provided good approximation to optimal result but they suffer from low efficiency. The excessively long execution time in application to large-scale social networks is also suffered. A framework is presented to accelerate the influence maximization using parallel processing with capability of graphics processing unit (GPU). Therefore, with the same objective accelerates the influence maximization by taking help of the parallel processing . It has been a NP hard problem. GPU implementation is used for improving existing greedy algorithms and designing a bottom-up traversal algorithm.

References
  1. Xiaodong Liu, Mo Li, Shanshan Li, ShaoliangPeng, Xiaopei Lu," IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks", IEEE Transaction on Parallel and Distributed Systems, VOL. 25, NO. 1, January 2014
  2. R. Zafaraniand H. Liu, "Social Computing Data RepositoryatASU,"http://socialcomputing. asu. edu/, Nov. 2012.
  3. D. Bader and K. Madduri,"GTgraph: A Suite of SyntheticGraphGenerators," http://www. cse. psu. edu/madduri/software/GTgraph/, Nov. 2012.
  4. J. Barnat, P. Bauch, L. Brim, and M. Ceska, "Computing Strongly Connected Components in Parallel on CUDA," Proc. IEEE 25th Int'l Parallel Distributed Processing Symp. (IPDPS), pp. 544-555, 2011.
  5. A. Goyal, W. Lu, and L. V. S. Lakshmanan, "CELF++: Optimizingthe Greedy Algorithm for Influence Maximization in Social Networks," Proc. Int'l Conf. World Wide Web (WWW), pp. 47- 48, 2011.
  6. Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie, "SimulatedAnnealing Based Influence Maximization in Social Networks,"Proc. 25th AAAI Int'l Conf. Artificial Intelligence (AAAI), pp. 127-132, 2011.
  7. V. Vineet, P. Harish, S. Patidar, and P. J. Narayanan, "Fast Minimum Spanning Tree for Large Graphs on the GPU," Proc. High Performance Graphics Conf. (HPG), pp. 167-171, 2010.
  8. Y. Wang, G. Cong, G. Song, and K. Xie, "Community-Based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks," Proc. ACM Int'l Conf. Knowledge Discovery and Data Mining (SIGKDD), pp. 1039-1048, 2010.
  9. W. Chen, Y. Wang, and S. Yang, "Efficient Influence Maximizationin Social Networks," Proc. ACM Int'l Conf. Knowledge Discovery and Data Mining (SIGKDD), pp. 199-208, 2009.
  10. N. Bell and M. Garland, "Efficient Sparse Matrix-Vector Multiplicationon CUDA," Technical Report NVR-2008-04, NVIDIA,Dec. 2008.
  11. P. Harish and P. J. Narayanan, "Accelerating Large Graph Algorithms on the GPU Using CUDA," Proc. High Performance Computing (HiPC), pp. 197-208, 2007.
  12. J. Leskovec, L. Adamic, and B. Huberman,"The Dynamics ofViral Marketing," ACM Trans. Web, vol. 1, no. 1, p. 5, May2007.
  13. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen,and N. Glance, "Cost-effective Outbreak Detection in Networks,"Proc. 13th ACM SIGKDD Int'l Conf. Knowledge Discovery and DataMining, 2007.
  14. D. Kempe, J. Kleinberg, and E. Tardos, "Maximizing the Spread of Influence through a Social Network," Proc. ACM Int'l Conf. Knowledge Discovery and Data Mining (SIGKDD), pp. 137- 146, 2003.
  15. E. Cohen, "Size-Estimation Framework with Applications toTransitive Closure and Reachability," J. Computer and SystemSciences, vol. 55, no. 3, pp. 441-453, 1997.
  16. X. Liu, S. Li, X. Liao, L. Wang, and Q. Wu, "In-Time Estimationfor Influence Maximization in Large-Scale Social Networks,"Proc. ACMEuroSys Workshop Social Network Systems, pp. 1-6,2012.
  17. S. H. Nobari, X. Lu, P. Karras, and S. Bressan, "Fast Random GraphGeneration," Proc. 14th Int'l Conf. Extending Database Technology(EDBT), pp. 331-342, 2011.
  18. H. Kwak, C. Lee, H. Park, and S. Moon, "What is Twitter, a SocialNetwork or a News Media?" Proc. Int'l Conf. World Wide Web(WWW), pp. 591-600, 2010.
  19. M. Richardson and P. Domingos, "Mining Knowledge-SharingSites for Viral Marketing," Proc. ACM Int'l Conf. KnowledgeDiscovery and Data Mining (SIGKDD), pp. 61-70, 2002.
  20. W. Chen, C. Wang, and Y. Wang, "Scalable Influence Maximizationfor Prevalent Viral Marketing in Large-Scale Social Networks,"Proc. ACM Int'l Conf. Knowledge Discovery and Data Mining(SIGKDD), pp. 1029-1038, 2010.
  21. N. Amato. Improved Processor Bounds for Parallel Algorithmsfor Weighted Directed Graphs. Information ProcessingLetters, 45(3):147–152, 1993.
  22. David A. Bader and KameshMadduri. Parallel algorithms for evaluating centrality indicesin real-world networks. In ICPP '06: Proceedings of the 2006 International Conference onParallel Processing, pages 539. 550, Washington, DC, USA, 2006. IEEE Computer Society.
  23. G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel:a system for large-scale graph processing. In SIGMOD, 2010.
  24. F. Benevenut, T. Rodrigues, M. Cha, and V. Almeida. Characterizing userbehavior in online social networks. In Proc. of ACM SIGCOMM InternetMeasurement Conference. ACM, 2009.
  25. J. Weng, E. -P. Lim, J. Jiang, and Q. He. Twitterrank: finding topic-sensitiveinfluential twitterers. In Proc. of the third ACM international conference on Websearch and data mining. ACM, 2010.
  26. S. Cris´ostomo, U. Schilcher, C. Bettstetter, andJ. Barros. Analysis of probabilistic flooding: How dowe choose the right coin. In IEEE ICC, 2009.
  27. J. H. Fowler, C. T. Dawes, and N. A. Christakis. Model of genetic variation in human social networks. PNAS, 106(6):1720–1724, 2009.
  28. D. Kempe, J. M. Kleinberg, and ´ E. Tardos. Maximizingthe spread of influence through a social network. In Proceedingsof the 9th ACM SIGKDD Conference on KnowledgeDiscovery and Data Mining, pages 137–146, 2003.
  29. M. Kimura and K. Saito. Tractable models for informationdiffusion in social networks. In Proceedings of the10th European Conference on Principles and Practiceof Knowledge Discovery in Databases, pages 259–271,2006.
Index Terms

Computer Science
Information Sciences

Keywords

Gpu Influence Maximization Cuda Buta.