Cited By
View all- Hsu BLu CChang MTseng CShen C(2024)Budget-Constrained Ego Network Extraction With Maximized WillingnessIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344616936:12(7692-7707)Online publication date: Dec-2024
Local Overlapping Spatial-aware Community Detection
Authors: 
Li Ni, Hefei Xu, Yiwen Zhang, Wenjian Luo, Yingying Huang, Victor S. ShengAuthors Info & Claims
Article No.: 59, Pages 1 - 21
Abstract
Local spatial-aware community detection refers to detecting a spatial-aware community for a given node using local information. A spatial-aware community means that nodes in the community are tightly connected in structure, and their locations are close to each other. Existing studies focus on detecting the local non-overlapping spatial-aware community, i.e., detecting a spatial-aware community containing the given node. However, many geosocial networks often contain overlapping spatial-aware communities. Therefore, we propose a local overlapping spatial-aware community detection (LOSCD) problem, which aims to detect all spatial-aware communities that contain a given node with local information. To address LOSCD problem, we design an algorithm based on Spatial Modularity and Edge Similarity, called SMES. SMES contains two processes: spatial expansion and structure detection. The spatial expansion process involves using spatial modularity to identify nodes that are spatially close, while the structural detection process employs edge similarity to identify nodes that are structurally close. Experimental results demonstrate that SMES outperforms comparison algorithms in terms of both structural and spatial cohesiveness.
References
[1]
Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. 2010. Link communities reveal multiscale complexity in networks. Nature 466, 7307 (2010), 761–764.
[2]
Ahmed Al-Baghdadi and Xiang Lian. 2020. Topic-based community search over spatial-social networks. Proc. VLDB Endow. 13, 11 (2020), 2104–2117.
[3]
Kamal Berahmand, Asgarali Bouyer, and Mahdi Vasighi. 2018. Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes. IEEE Trans. Computat. Soc. Syst. 5, 4 (2018), 1021–1033.
[4]
Jiang Bian, Haoyi Xiong, Yanjie Fu, and Sajal K. Das. 2018. CSWA: Aggregation-free spatial-temporal community sensing. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI Press, 2087–2094.
[5]
Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2017. Metrics for community analysis: A survey. Comput. Surv. 50, 4 (2017), 1–37.
[6]
Xuanhao Chen, Liwei Deng, Yan Zhao, Xiaofang Zhou, and Kai Zheng. 2021. Community-based influence maximization in location-based social network. World Wide Web 24, 6 (2021), 1903–1928.
[7]
Yilin Chen and Jack W. Baker. 2021. Community detection in spatial correlation graphs: Application to non-stationary ground motion modeling. Comput. Geosci. 154 (2021), 104779.
[8]
Yu Chen, Jun Xu, and Minzheng Xu. 2015. Finding community structure in spatially constrained complex networks. Int. J. Geog. Inf. Sci. 29, 6 (2015), 889–911.
[9]
Aaron Clauset, Mark E. J. Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Phys. Rev. E 70, 6 (2004), 066111.
[10]
Michele Coscia, Giulio Rossetti, Fosca Giannotti, and Dino Pedreschi. 2012. DEMON: A local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’12), Qiang Yang, Deepak Agarwal, and Jian Pei (Eds.). ACM, 615–623.
[11]
Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, and Wei Wang. 2013. Online search of overlapping communities. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’13). 277–288.
[12]
Alessandro Epasto, Silvio Lattanzi, and Renato Paes Leme. 2017. Ego-splitting framework: From non-overlapping to overlapping clusters. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 145–154.
[13]
Paul Expert, Tim S. Evans, Vincent D. Blondel, and Renaud Lambiotte. 2011. Uncovering space-independent communities in spatial networks. Proc. Nat. Acad. Sci. 108, 19 (2011), 7663–7668.
[14]
Yixiang Fang, Reynold Cheng, Xiaodong Li, Siqiang Luo, and Jiafeng Hu. 2017. Effective community search over large spatial graphs. Proc. VLDB Endow. 10, 6 (2017), 709–720.
[15]
Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020. A survey of community search over big graphs. VLDB J. 29, 1 (2020), 353–392.
[16]
Yixiang Fang, Zheng Wang, Reynold Cheng, Xiaodong Li, Siqiang Luo, Jiafeng Hu, and Xiaojun Chen. 2019. On spatial-aware community search. IEEE Trans. Knowl. Data Eng. 31, 4 (2019), 783–798.
[17]
Song Gao, Yu Liu, Yaoli Wang, and Xiujun Ma. 2013. Discovering spatial interaction communities from mobile phone data. Trans. GIS 17, 3 (2013), 463–481.
[18]
Mohammad Ghane’i-Ostad, Hamed Vahdat-Nejad, and Majid Abdolrazzagh-Nezhad. 2018. Detecting overlapping communities in LBSNs by fuzzy subtractive clustering. Soc. Netw. Anal. Min. 8, 1 (2018), 23.
[19]
Kun Guo, Xintong Huang, Ling Wu, and Yuzhong Chen. 2022. Local community detection algorithm based on local modularity density. Appl. Intell. 52, 2 (2022), 1238–1253.
[20]
Alexandre Hollocou, Thomas Bonald, and Marc Lelarge. 2017. Multiple local community detection. SIGMETRICS Perform. Eval. Rev. 45, 3 (2017), 76–83.
[21]
Ye Hong and Yao Yao. 2019. Hierarchical community detection and functional area identification with OSM roads and complex graph theory. Int. J. Geog. Inf. Sci. 33, 8 (2019), 1569–1587.
[22]
Dany Kamuhanda, Meng Wang, and Kun He. 2020. Sparse nonnegative matrix factorization for multiple-local-community detection. IEEE Trans. Computat. Soc. Syst. 7, 5 (2020), 1220–1233.
[23]
Junghoon Kim, Tao Guo, Kaiyu Feng, Gao Cong, Arijit Khan, and Farhana Murtaza Choudhury. 2020. Densely connected user community and location cluster search in location-based social networks. In Proceedings of the International Conference on Management of Data. ACM, 2199–2209.
[24]
Hui Li, Ke Deng, Jiangtao Cui, Zhenhua Dong, Jianfeng Ma, and Jianbin Huang. 2018. Hidden community identification in location-based social network via probabilistic venue sequences. Inf. Sci. 422 (2018), 188–203.
[25]
Yixuan Li, Kun He, David Bindel, and John E. Hopcroft. 2015. Uncovering the small community structure in large networks: A local spectral approach. In Proceedings of the 24th International Conference on World Wide Web (WWW’15), Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi (Eds.). ACM, 658–668.
[26]
Ankita Likhyani, Vinayak Gupta, Srijith P. K., Deepak P., and Srikanta Bedathur. 2020. Modeling implicit communities from geo-tagged event traces using spatio-temporal point processes. In Proceedings of the 21st International Conference on Web Information Systems Engineering. Springer, 153–169.
[27]
Feng Luo, James Z. Wang, and Eric Promislow. 2008. Exploring local community structures in large networks. Web Intell. Agent Syst.: Int. J. 6, 4 (2008), 387–400.
[28]
Wenjian Luo, Nannan Lu, Li Ni, Wenjie Zhu, and Weiping Ding. 2020. Local community detection by the nearest nodes with greater centrality. Inf. Sci. 517 (2020), 377–392.
[29]
Puneet Manchanda, Grant Packard, and Adithya Pattabhiramaiah. 2015. Social dollars: The economic impact of customer participation in a firm-sponsored online customer community. Market. Sci. 34, 3 (2015), 367–387.
[30]
Atsushi Miyauchi and Yasushi Kawase. 2015. What is a network community? A novel quality function and detection algorithms. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. 1471–1480.
[31]
Li Ni, Junnan Ge, Yiwen Zhang, Wenjian Luo, and Victor S. Sheng. 2023. Semi-supervised local community detection. IEEE Trans. Knowl. Data Eng. (2023), 1–17. DOI:
[32]
Li Ni, Wenjian Luo, Wenjie Zhu, and Bei Hua. 2020. Local overlapping community detection. ACM Trans. Knowl. Discov. Data 14, 1 (2020), 3:1–3:25.
[33]
Li Ni, Hefei Xu, Yiwen Zhang, and Wenjian Luo. 2023. Spatial-aware local community detection guided by dominance relation. IEEE Trans. Computat. Soc. Syst. 10, 2 (2023), 686–699.
[34]
Mehrdad Rostami, Mourad Oussalah, Kamal Berahmand, and Vahid Farrahi. 2023. Community detection algorithms in healthcare applications: A systematic review. IEEE Access 11 (2023), 30247–30272.
[35]
Kai Wang, Xin Cao, Xuemin Lin, Wenjie Zhang, and Lu Qin. 2018. Efficient computing of radius-bounded k-cores. In Proceedings of the IEEE 34th International Conference on Data Engineering. 233–244.
[36]
Longfei Wang, Yong Zeng, Yixin Li, Zhihong Liu, Jianfeng Ma, and Xiaoyan Zhu. 2019. Research on resolution limit of community detection in location-based social networks. In Proceedings of the International Conference on Networking and Network Applications. 90–95.
[37]
Yanjun Wang, Liang Zhu, Jiangtao Ma, Guangwu Hu, Jiangchuan Liu, and Yaqiong Qiao. 2021. Knowledge graph-based spatial-aware user community preference query algorithm for LBSNs. Big Data Res. 23 (2021), 100169.
[38]
Zhu Wang, Daqing Zhang, Dingqi Yang, Zhiyong Yu, and Xingshe Zhou. 2012. Detecting overlapping communities in location-based social networks. In Proceedings of the 4th International Conference on Social Informatics. Springer, 110–123.
[39]
Zhu Wang, Daqing Zhang, Xingshe Zhou, Dingqi Yang, Zhiyong Yu, and Zhiwen Yu. 2014. Discovering and profiling overlapping communities in location-based social networks. IEEE Trans. Syst., Man, Cybern.: Syst. 44, 4 (2014), 499–509.
[40]
Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ‘small’ networks. Nature 393, 6684 (1998), 440–442.
[41]
Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon. 2016. Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans. Knowl. Data Eng. 28, 5 (2016), 1272–1284.
[42]
Zhao-lei Xiong, Chun-he Xia, Bo Sun, and Mei-jia Hou. 2019. Mining similarity of users in location-based social networks for discovering overlapping communities. In Recent Developments in Intelligent Computing, Communication and Devices. Springer, 417–428.
[43]
Changqiao Xu, Liang Zhu, Yang Liu, Jianfeng Guan, and Shui Yu. 2021. DP-LTOD: Differential privacy latent trajectory community discovering services over location-based social networks. IEEE Trans. Serv. Comput. 14, 4 (2021), 1068–1083.
[44]
Shuai Xu, Jiuxin Cao, Xuelin Zhu, Yi Dong, and Bo Liu. 2018. Community discovery based on social relations and temporal-spatial topics in LBSNs. In Proceedings of the 2nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Springer, 206–217.
[45]
Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 587–596.
[46]
Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM’13), Stefano Leonardi, Alessandro Panconesi, Paolo Ferragina, and Aristides Gionis (Eds.). ACM, 587–596.
[47]
Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. When engagement meets similarity: Efficient (k, r)-core computation on social networks. Proc. VLDB Endow. 10, 10 (2017), 998–1009.
[48]
Qijun Zhu, Haibo Hu, Cheng Xu, Jianliang Xu, and Wang-Chien Lee. 2017. Geo-social group queries with minimum acquaintance constraints. VLDB J. 26, 5 (2017), 709–727.
Index Terms
- Local Overlapping Spatial-aware Community Detection
Recommendations
Local Community Detection in Multiple Private Networks
Individuals are often involved in multiple online social networks. Considering that owners of these networks are unwilling to share their networks, some global algorithms combine information from multiple networks to detect all communities in multiple ...
Local Overlapping Community Detection
Local community detection refers to finding the community that contains the given node based on local information, which becomes very meaningful when global information about the network is unavailable or expensive to acquire. Most studies on local ...
A robust two-stage algorithm for local community detection
Local community detection addresses the efficiency problem faced by global community detection. Most existing local community detection algorithms take a seed as an initial community. They extend the community by running a greedy optimization process ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
663 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 January 2024
Online AM: 27 November 2023
Accepted: 17 November 2023
Revised: 25 August 2023
Received: 16 April 2023
Published in TKDD Volume 18, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Natural Science Foundation of China
- Natural Science Foundation of Anhui Province of China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 397Total Downloads
- Downloads (Last 12 months)378
- Downloads (Last 6 weeks)25
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View all- Hsu BLu CChang MTseng CShen C(2024)Budget-Constrained Ego Network Extraction With Maximized WillingnessIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344616936:12(7692-7707)Online publication date: Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in