Username   Password       Forgot your password?  Forgot your username? 


A Top-r k Influential Community Search Algorithm

Volume 14, Number 11, November 2018, pp. 2553-2560
DOI: 10.23940/ijpe.18.11.p1.25532560

Wei Chena,b, Jia Liua,b, Ziyang Chena,c, and Jianqi Chena

aSchool of Information Science and Engineering, Yanshan University, Qinhuangdao, 066004, China
bDepartment of Information Engineering, Hebei University of Environmental Engineering, Qinhuangdao, 066102, China
cSchool of Information and Management, Shanghai Lixin University of Accounting and Finance, Shanghai, 201620, China

(Submitted on August 6, 2018; Revised on September 10, 2018; Accepted on October 26, 2018)


Top-r k influential community search is one of the hot topics in social network research, the solution of which usually adapts the “index + query” strategy. Aiming at the problems of low index efficiency and unreasonable metric of the influence, we first propose a new index construction method that not only improves the efficiency of constructing index but also reduces the index size. In the community search, the metric of the influence on the community is redefined and the search algorithm is proposed on this basis to make the search results more practical. Finally, according to experiments on 12 datasets, we verify the high efficiency of the method proposed in this paper compared with the existing methods from the following aspects including the index construction time, the index size, and the search time.


References: 21

                  1. S. Fortunato, “Community Detection in Graphs,” Physics Reports, Vol. 486, No. 3, pp. 75-174, 2010
                  2. M. Girvan and M. Newman, “Community Structure in Social and Biological Networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, No. 12, pp. 7821-7826, 2002
                  3. K. U. Khan, N. A. Tu, M. R. Akhond, W. Nawaz, and Y. K. Lee, “Accelerating Community-Search Problem through Faster Graph Dedensification,” in Proceedings of IEEE International Conference on Big Data and Smart Computing, pp. 340-347, JEJU, Korea, February, 2017
                  4. M. Newman and M. Girvan, “Finding and Evaluating Community Structure in Networks,” Physical Review E: Statistical, Nonlinear & Soft Matter Physics, Vol. 69, No. 2, pp. 026113, 2004
                  5. M. Sozio and A. Gionis, “The Community-Search Problem and How to Plan a Successful Cocktail Party,” in Proceedings of 16th ACM Sigkdd International Conference on Knowledge Discovery & Data Mining, pp. 939-948, Washington, USA, July 2010
                  6. A. Broder, R. Kumar, F. Maghoul, et al., “Graph Structure in the Web: Experiments and Models,” the International Journal of Computer and Telecommunications Networking, Vol. 33, pp. 309-320, May 2000
                  7. G. O. Roberts and J. S. Rosenthal, “Downweighting Tightly Knit Communities in World Wide Web Rankings,” Advances & Applications in Statistics, Vol. 3, No. 3, pp. 199-216, 2003
                  8. G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society,” Nature, Vol. 435, No. 7043, pp. 814-818, 2005
                  9. G. Su, A. Kuchinsky, J. H. Morris, D. J. States, and F. Meng, “Glay: Community Structure Analysis of Biological Networks,” Bioinformatics, Vol. 26, No. 24. pp. 3135-3137, 2010
                  10. R. Guimera and L. A. N. Amaral, “Functional Cartography of Complex Metabolic Networks,” Nature, Vol. 433, No. 7028, pp. 895-900, 2005
                  11. C. E. Lawson, W. Sha, A. S. Bhattacharjee, J. J. Hamilton, K. D. Mcmahon, and R. Goel, “Metabolic Network Analysis Reveals Microbial Community Interactions in Anammox Granules,” Nature Communications, Vol. 8, pp. 15416, 2017
                  12. Z. Hu, X. Wang and K. Xu, “Mining Community in Social Network Using Call Detail Records,” in Proceedings of International Conference on Fuzzy Systems and Knowledge Discovery, pp. 1641-1645, Chongqing, China, May 2012
                  13. S. Sharma and G. N. Purohit, “A New Centrality Measure for Tracking Online Community in Social Network,” International Journal of Information Technology & Computer Science, Vol. 4, No. 4, 2012
                  14. P. Chen and S. Redner, “Community Structure of the Physical Review Citation Network,” Journal of Informetrics, Vol. 4, No. 3, pp. 278-290, 2010
                  15. F. K. H. Phoa and L. H. Chang, “A Study of the Article Citation Network in Statistics Research Community,” in Proceedings of Iiai International Congress on Advanced Applied Informatics, pp. 134-137, Hamamatsu, Japan, July 2017
                  16. R. H. Li, Q. Lu, J. X. Yu, and R. Mao, “Influential Community Search in Large Networks,” Proceedings of the VLDB Endowment, Vol. 8, No. 5, pp. 509-520, 2015
                  17. G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, “K-Core Organization in Complex Networks,”. Experimental Aging Research, Vol. 15, No. 1-2, pp. 13-8, 2012
                  18. S. Janson and M. J. Luczak. “A Simple Solution to the K-Core Problem,” Random Structures & Algorithms, Vol. 30, No. 1-2, pp. 50-62, 2007
                  19. A. Montresor, F. D. Pellegrini, and D. Miorandi, “Distributed K-Core Decomposition,” IEEE Transactions on Parallel & Distributed Systems, Vol. 24, No. 2, pp. 288-300, 2013
                  20. M. Newman, “Detecting Community Structure in Networks,” European Physical Journal B, Vol. 38, No. 2, pp. 321-330, 2004
                  21. S. B. Seidman, “Network Structure and Minimum Degree,” Social Networks, Vol. 5, No. 3, pp. 269-287, 1983


                                  Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

                                  This site uses encryption for transmitting your passwords.