A Top-r k Influential Community Search Algorithm
Volume 14, Number 11, November 2018, pp. 2553-2560 DOI: 10.23940/ijpe.18.11.p11.26522662
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)
Abstract:
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
- S. Fortunato, “Community Detection in Graphs,” Physics Reports, Vol. 486, No. 3, pp. 75-174, 2010
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- R. Guimera and L. A. N. Amaral, “Functional Cartography of Complex Metabolic Networks,” Nature, Vol. 433, No. 7028, pp. 895-900, 2005
- 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
- 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
- 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
- P. Chen and S. Redner, “Community Structure of the Physical Review Citation Network,” Journal of Informetrics, Vol. 4, No. 3, pp. 278-290, 2010
- 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
- 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
- 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
- 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
- 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
- M. Newman, “Detecting Community Structure in Networks,” European Physical Journal B, Vol. 38, No. 2, pp. 321-330, 2004
- 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. |