A Top-r k Influential Community Search Algorithm

doi:10.23940/ijpe.18.11.p11.26522662

Int J Performability Eng ›› 2018, Vol. 14 ›› Issue (11): 2652-2662.doi: 10.23940/ijpe.18.11.p11.26522662

Previous Articles Next Articles

A Top-r k Influential Community Search Algorithm

Wei Chen^{a, b}, Jia Liu^{a, b, *}, Ziyang Chen^{a, c}, and Jianqi Chen^a

^a School of Information Science and Engineering, Yanshan University, Qinhuangdao, 066004, China;
^b Department of Information Engineering, Hebei University of Environmental Engineering, Qinhuangdao, 066102, China;
^c School of Information and Management, Shanghai Lixin University of Accounting and Finance, Shanghai, 201620, China

Submitted on ;
Contact: * E-mail address: liujia78928@126.com
About author:Wei Chen is currently working toward a Ph.D. in the Department of Computer Science and Technology at Yanshan University, Qinhuangdao, China. She is also an associate professor. Her research interests include query processing on graph data.Jia Liu is currently working toward a Ph.D. in the Department of Computer Science and Technology at Yanshan University, Qinhuangdao, China. She is also an associate professor. Her research interests include querying and processing on spatial information.Ziyang Chen received his B.S. degree, M.S. degree, and Ph.D. in Computer Science from Yanshan University, Qinhuangdao, China in 1996, 2000, and 2009, respectively. He is currently a Ph.D. supervisor and distinguished professor at Shanghai Lixin University of Accounting and Finance. His research interests include database theory and techniques.Jianqi Chen is currently working toward an M.S. degree in the Department of Computer Science and Technology at Yanshan University, Qinhuangdao, China. Her research interests include query processing on graph data.

Abstract

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.

Key words: community search, influential community, index

Wei Chen, Jia Liu, Ziyang Chen, and Jianqi Chen. A Top-r k Influential Community Search Algorithm [J]. Int J Performability Eng, 2018, 14(11): 2652-2662.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

[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,Y. K. Lee, “Accelerating Community-Search Problem through Faster Graph Dedensification,” inProceedings 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,” inProceedings 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,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,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,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,” inProceedings 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,” inProceedings of Iiai International Congress on Advanced Applied Informatics, pp. 134-137, Hamamatsu, Japan, July 2017
[16] R. H. Li, Q. Lu, J. X. Yu,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,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,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

A Top-r k Influential Community Search Algorithm

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended 0

[1]	M. S. Yahaya, N. Azis, H. Zainuddin, M. F. Basar, and M. H. Harun. Comparison of Health Index and Degree of Polymerization based on 2-Furfuraldehyde Compound for Transformer Condition Estimation [J]. Int J Performability Eng, 2022, 18(9): 654-659.
[2]	Mamta Bhamare, and K Ashokkumar. Personality Prediction through Social Media Posts [J]. Int J Performability Eng, 2022, 18(11): 817-825.
[3]	Rahul Ray, Shiva Shankar Choudhary, and Lal Bahadur Roy. Reliability Analysis of Layered Soil Slope Stability using ANFIS and MARS Soft Computing Techniques [J]. Int J Performability Eng, 2021, 17(7): 647-656.
[4]	Saurav Shekhar Kar and Lal Bahadur Roy. Reliability Analysis of a Finite Slope Considering the Effects of Soil Uncertainty [J]. Int J Performability Eng, 2021, 17(5): 473-483.
[5]	Divya Mohan and Latha Ravindran Nair. Probit Regressive Tversky Indexed Rocchio Convolutive Deep Neural Learning for Legal Document Data Analytics [J]. Int J Performability Eng, 2021, 17(10): 837-847.
[6]	Yuan Liang, Hongfang Cheng, and Wangshun Chen. Building Energy Consumption Data Index Method in Cloud Computing Environment [J]. Int J Performability Eng, 2020, 16(5): 747-756.
[7]	Xiulian Tang and Guoqiang Zhou. Grey Weighted QoS Evaluation based on Real-Time Scene [J]. Int J Performability Eng, 2020, 16(4): 569-576.
[8]	Wei Cui, An-Wei Wan, Jun-Chao Feng, and Zhi-Yuan Zhu. Analysis of Local Government Behaviors and Technology Decomposition of Carbon Emission Reduction under Hard Environmental Protection Constraints [J]. Int J Performability Eng, 2020, 16(2): 195-202.
[9]	Tao Yan, In-Ho Ra, Hui Wen, Hang Xu, and Linyun Huang. Bit Allocation Algorithm based on SSIM for 3D Video Coding [J]. Int J Performability Eng, 2019, 15(7): 1813-1821.
[10]	Chih-Hsuan Huang, Yii-Ching Lee, and Hsin-Hung Wu. Framework of Monitoring Patient Safety Culture by the Bootstrap Method [J]. Int J Performability Eng, 2019, 15(5): 1326-1333.
[11]	Jiaojiao Guo and Hailin Feng. Dynamic Reliability Maintenance for Complex Systems using the Survival Signature [J]. Int J Performability Eng, 2019, 15(5): 1343-1351.
[12]	Zhiqian Wang, Baoquan Mao, Yongliang Wu, Xianghua Bai, Shuai Feng, Xiaoping Han, Cheng Li, and Tu Lan. Optimization of Dynamic Characteristics of Automatic-Firing Muzzle with Damping [J]. Int J Performability Eng, 2019, 15(1): 1-12.
[13]	Jianwei Gao and Huicheng Liu. A Risk-Free Protection Index Model for Multi-Objective Uncertain Portfolio Selection with Entropy and Variance Constraints [J]. Int J Performability Eng, 2018, 14(12): 3129-3139.