Scalable Spatio-temporal Top-k Interaction Queries on Dynamic Communities
Article No.: 6, Pages 1 - 25
Abstract
Social media platforms generate massive amounts of data that reveal valuable insights about users and communities at large. Existing techniques have not fully exploited such data to help practitioners perform a deep analysis of large online communities. Lack of scalability hinders analyzing communities of large sizes and requires tremendous system resources and unacceptable runtime. This article proposes a new analytical query that identifies the top-k posts that a given user community has interacted with during a specific time interval and within a spatial range. We propose a novel indexing framework that captures the interactions of users and communities to provide a low query latency. Moreover, we propose exact and approximate algorithms to process the query efficiently and utilize the index content to prune the search space. The extensive experimental evaluation on real data has shown the superiority of our techniques and their scalability to support large online communities.
References
[1]
[n. d.]. Retrieved from http://neo4j.org/
[2]
[n. d.]. Facebook. Retrieved from https://www.facebook.com/
[3]
[n. d.]. LinkedIn. Retrieved from https://www.linkedin.com/
[4]
2019. List of Virtual Communities with More Than 1 Million Users. Retrieved from http://www.worldheritage.org/articles
[5]
Nitin Agarwal, Huan Liu, Lei Tang, and Philip S. Yu. 2008. Identifying the influential bloggers in a community. In Proceedings of the ACM International Conference on Web Search and Data Mining. 207–218.
[6]
Nesreen K. Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. 2014. Graph sample and hold: A framework for big-graph analytics. In Proceedings of the SIGKDD Conference. 1446–1455.
[7]
Christopher Aicher, Abigail Z. Jacobs, and Aaron Clauset. 2015. Learning latent block structure in weighted networks. J. Complex Netw. 3, 2 (2015), 221–248.
[8]
Abdullah Almaatouq, Ahmad Alabdulkareem, Mariam Nouh, Erez Shmueli, Mansour Alsaleh, Vivek K. Singh, Abdulrahman Alarifi, Anas Alfaris, and Alex Pentland. 2014. Twitter: Who gets caught? Observed trends in social micro-blogging spam. In Proceedings of the ACM Conference on Web Science. 33–41.
[9]
Abdulaziz Almaslukh, Yongyi Liu, and Amr Magdy. 2021. Scalable spatio-temporal top-k community interactions query. In Proceedings of the 29th International Conference on Advances in Geographic Information Systems. 293–296.
[10]
Abdulaziz Almaslukh and Amr Magdy. 2019. Temporal geo-social personalized search over streaming data. In Proceedings of the SIGSPATIAL Conference. 189–198.
[11]
Nicky Antonius and L. Rich. 2013. Discovering collection and analysis techniques for social media to improve public safety. Int. Technol. Manag. Rev. 3, 1 (2013), 42–53.
[12]
P. Bahl, R. Chancre, and J. Dungeon. 2016. GraphJet: Real-time content recommendations at Twitter. In VLDB Endowment, VLDB Endowment, 1281–1292.
[13]
Radoslav Baltezarevic, Borivoje Baltezarevic, Piotr Kwiatek, and Vesna Baltezarevic. 2019. The impact of virtual communities on cultural identity. Symposion 6, 1 (2019), 7–22.
[14]
Hamid Ahmadi Beni and Asgarali Bouyer. 2020. TI-SC: Top-k influential nodes selection based on community detection and scoring criteria in social networks. J. Amb. Intell. Hum. Comput. 11 (2020), 1–20.
[15]
Lisi Chen, Gao Cong, Christian S. Jensen, and Dingming Wu. 2013. Spatial keyword query processing: An experimental evaluation. Proc. VLDB Endow. 6, 3 (2013), 217–228.
[16]
Lu Chen, Chengfei Liu, Rui Zhou, Jianxin Li, Xiaochun Yang, and Bin Wang. 2018. Maximum co-located community search in large scale social networks. Proc. VLDB Endow. 11, 10 (2018), 1233–1246.
[17]
Mingming Chen, Konstantin Kuzmin, and Boleslaw K. Szymanski. 2014. Community detection via maximization of modularity and its variants. IEEE Trans. Computat. Soc. Syst. 1, 1 (2014), 46–65.
[18]
Chennai Floods 2017. How Twitter, Facebook, WhatsApp and Other Social Networks Are Saving Lives During Disasters. Retrieved from http://www.huffingtonpost.in/2017/01/31/how-twitter-facebook-whatsapp-and-other-social-networks-are-sa_a_21703026/
[19]
Coronavirus 2020. Here’s How Social Media Can Combat the Coronavirus Infodemic. Retrieved from https://www.technologyreview.com/s/615368/facebook-twitter-social-media-infodemic-misinformation/
[20]
Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, and Wei Wang. 2013. Online search of overlapping communities. In Proceedings of the SIGMOD Conference. 277–288.
[21]
Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local search of communities in large graphs. In Proceedings of the SIGMOD Conference. 991–1002.
[22]
Thu-Lan Dam, Sean Chester, Kjetil Nørvåg, and Quang-Huy Duong. 2021. Efficient top-k recently-frequent term querying over spatio-temporal textual streams. Inf. Syst. 97 (2021), 101687.
[23]
Daniel J. DiTursi, Gaurav Ghosh, and Petko Bogdanov. 2017. Local community detection in dynamic networks. In Proceedings of the International Conference on Data Mining. 847–852.
[24]
Jian Dong, Bin Chen, Chuan Ai, Liang Liu, and Fang Zhang. 2018. A degree-based distributed label propagation algorithm for community detection in networks. In Proceedings of the 4th ACM SIGSPATIAL International Workshop on Safety and Resilience. 1–5.
[25]
Facebook Stats 2019. 53 Incredible Facebook Statistics and Facts. Retrieved from https://www.brandwatch.com/blog/facebook-statistics/
[26]
Facebook Stats Teen 2020. Distribution of Facebook Users in the United States. Retrieved from https://www.statista.com/statistics/187549/facebook-distribution-of-users-age-group-usa/
[27]
Ronald Fagin, Amnon Lotem, and Moni Naor. 2003. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66, 4 (2003), 614–656.
[28]
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.
[29]
Yixiang Fang, Reynold Cheng, Siqiang Luo, and Jiafeng Hu. 2016. Effective community search for large attributed graphs. Proc. VLDB Endow. 9, 12 (2016), 1233–1244.
[30]
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.
[31]
Greg Fisher. 2019. Online communities and firm advantages. Acad. Manag. Rev. 44, 2 (2019), 279–298.
[32]
Nick Fox and Chris Roberts. 1999. GPs in cyberspace: The sociology of a ‘‘virtual community.’’ Sociolog Rev 47, 4 (1999), 643–671.
[33]
Theodore Georgiou, Amr El Abbadi, and Xifeng Yan. 2017. Extracting topics with focused communities for social content recommendation. In Proceedings of the ACM Conference on Computer Supported Cooperative Work and Social Computing. 1432–1443.
[34]
Steve Harenberg, Gonzalo Bello, La Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kanchana Padmanabhan, and Nagiza Samatova. 2014. Community detection in large-scale networks: A survey and empirical evaluation. Wiley Interdiscip. Rev.: Computat. Stat. 6, 6 (2014), 426–439.
[35]
Abdeltawab M. Hendawi and Mohamed F. Mokbel. 2012. Predictive spatio-temporal queries: A comprehensive survey and future directions. In Proceedings of the 1st ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems. 97–104.
[36]
Tuan-Anh Hoang-Vu, Huy T. Vo, and Juliana Freire. 2016. A unified index for spatio-temporal keyword queries. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 135–144.
[37]
Han Hu, NhatHai Phan, Xinyue Ye, Ruoming Jin, Kele Ding, Dejing Dou, and Huy T. Vo. 2019. DrugTracker: A community-focused drug abuse monitoring and supporting system using social media and geospatial data (demo paper). In Proceedings of the SIGSPATIAL Conference. 564–567.
[38]
Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In Proceedings of the SIGMOD Conference. 1311–1322.
[39]
Hurricane Dorian 2019. How Social Media Is Helping Survivors of Hurricane Dorian in the Bahamas. Retrieved from https://www.newyorker.com/news/news-desk/how-social-media-is-helping-survivors-of-hurricane-dorian-in-the-bahamas
[40]
IG Stats Teen 2021. Instagram by the Numbers: Stats, Demographics & Fun Facts. Retrieved from https://www.omnicoreagency.com/instagram-statistics/
[41]
IG Stats Teen 2021. Most Popular Social Networks of Teenagers in the United States from Fall 2012 to Fall 2020. Retrieved from https://www.statista.com/statistics/250172/social-network-usage-of-us-teens-and-young-adults/
[42]
Martin Junghanns, André Petermann, Martin Neumann, and Erhard Rahm. 2017. Management and analysis of big graph data: Current systems and open challenges. In Handbook of Big Data Technologies, Springer, 457–505.
[43]
Bisma S. Khan and Muaz A. Niazi. 2017. Network community detection: A review and visual survey. arXiv preprint arXiv:1708.00977 (2017).
[44]
Jungeun Kim and Jae-Gil Lee. 2015. Community detection in multi-layer graphs: A survey. ACM SIGMOD Rec. 44, 3 (2015), 37–48.
[45]
Reinout Kleinhans, Maarten Van Ham, and Jennifer Evans-Cowley. 2015. Using social media and mobile technologies to foster engagement and self-organization in participatory urban planning and neighbourhood governance. Planning Practice & Research (2015).
[46]
Jimmy Lin and Michael Schatz. 2010. Design patterns for efficient graph algorithms in MapReduce. In Proceedings of the 8th Workshop on Mining and Learning with Graphs.
[47]
Xiping Liu, Changxuan Wan, Neal N. Xiong, Dexi Liu, Guoqiong Liao, and Song Deng. 2018. What happened then and there: Top-k spatio-temporal keyword query. Inf. Sci. 453 (2018), 281–301.
[48]
Zhi Liu and Yan Huang. 2014. Community detection from location-tagged networks. In Proceedings of the SIGSPATIAL Conference. 525–528.
[49]
Ahmed R. Mahmood, Sri Punni, and Walid G. Aref. 2019. Spatio-temporal access methods: A survey (2010–2017). GeoInformatica 23 (2019), 1–36.
[50]
Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: A system for large-scale graph processing. In Proceedings of the SIGMOD Conference. 135–146.
[51]
Deepanshu Malhotra. 2021. Community detection in complex networks using link strength-based hybrid genetic algorithm. SN Comput. Sci. 2, 1 (2021), 1–16.
[52]
Shohei Matsugu, Hiroaki Shiokawa, and Hiroyuki Kitagawa. 2021. Fast algorithm for attributed community search. Journal of Information Processing 29 (2021), 188–196.
[53]
Daniel Memmi. 2008. The nature of virtual communities. In Cognition, Communication and Interaction, Springer, 70–82.
[54]
Robert Munro. 2013. Crowdsourcing and the crisis-affected community. Inf. Retriev. 16, 2 (2013), 210–266.
[55]
Seth A. Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin. 2014. Information network or social network? The structure of the Twitter follow graph. In Proceedings of the 23rd International Conference on World Wide Web. 493–498.
[56]
Preslav Nakov, Doris Hoogeveen, Lluís Màrquez, Alessandro Moschitti, Hamdy Mubarak, Timothy Baldwin, and Karin Verspoor. 2019. SemEval-2017 task 3: Community question answering. arXiv preprint arXiv:1912.00730 (2019).
[57]
Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos. 2012. Community detection in social media. Data Min. Knowl. Discov. 24, 3 (2012), 515–554.
[58]
Michel Plantié and Michel Crampes. 2013. Survey on social community detection. In Social Media Retrieval, Springer, 65–85.
[59]
Constance Elise Porter. 2004. A typology of virtual communities: A multi-disciplinary foundation for future research. J. Comput.-mediat. Commun. 10, 1 (2004), JCMC1011.
[60]
Jenny Preece and Diane Maloney-Krichmar. 2005. Online communities: Design, theory, and practice. J. Comput.-mediat. Commun. 10, 4 (2005), JCMC10410.
[61]
Lu Qin, Jeffrey Xu Yu, Lijun Chang, Hong Cheng, Chengqi Zhang, and Xuemin Lin. 2014. Scalable big graph processing in MapReduce. In Proceedings of the SIGMOD Conference. 827–838.
[62]
Anjum Razzaque and Tillal Eldabi. 2018. Assessing the impact of physicians’ virtual communities on their medical decision making quality. In Proceedings of the 51st Hawaii International Conference on System Sciences.
[63]
Joao B. Rocha-Junior, Orestis Gkorgkas, Simon Jonassen, and Kjetil Nørvåg. 2011. Efficient processing of top-k spatial keyword queries. In Proceedings of the 12th International Symposium on Advances in Spatial and Temporal Databases (SSTD’11). Springer, 205–222.
[64]
Arif Mohaimin Sadri, Samiul Hasan, Satish V. Ukkusuri, and Manuel Cebrian. 2017. Understanding information spreading in social media during Hurricane Sandy: User activity and network properties. arXiv preprint arXiv:1706.03019 (2017).
[65]
Arif Mohaimin Sadri, Samiul Hasan, Satish V. Ukkusuri, and Manuel Cebrian. 2020. Exploring network properties of social media interactions and activities during Hurricane Sandy. Transport. Res. Interdiscip. Perspect. 6 (2020), 100143.
[66]
Arif Mohaimin Sadri, Samiul Hasan, Satish V. Ukkusuri, and Juan Esteban Suarez Lopez. 2018. Analysis of social interaction network properties and growth on Twitter. Soc. Netw. Anal. Min. 8 (2018), 1–13.
[67]
Bin Shao, Haixun Wang, and Yatao Li. 2012. The trinity graph engine. Microsoft Res. 54 (2012), 4.
[68]
Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In Proceedings of the SIGKDD Conference. 939–948.
[69]
Ivan Srba and Maria Bielikova. 2016. A comprehensive survey and classification of approaches for community question answering. ACM Trans. Web 10, 3 (2016), 1–63.
[70]
Beiming Sun and Vincent T. Y. Ng. 2012. Identifying influential users by their postings in social networks. In Ubiquitous Social Media Analysis. 128–151.
[71]
Wen Sun, Achille Fokoue, Kavitha Srinivas, Anastasios Kementsietsidis, Gang Hu, and Guotong Xie. 2015. SQLGraph: An efficient relational-based property graph store. In Proceedings of the SIGMOD Conference. 1887–1901.
[72]
Lei Tang and Huan Liu. 2010. Community detection and mining in social media. Synthes. Lect. Data Min. Knowl. Discov. 2, 1 (2010), 1–137.
[73]
Xuning Tang and Christopher C. Yang. 2010. Identifying influential users in an online healthcare social network. In Proceedings of the IEEE International Conference on Intelligence and Security Informatics. 43–48.
[74]
G. Alan Wang, Jian Jiao, Alan S. Abrahams, Weiguo Fan, and Zhongju Zhang. 2013. ExpertRank: A topic-aware expert finding algorithm for online knowledge communities. Decis. Supp. Syst. 54, 3 (2013), 1442–1451.
[75]
Hongzhi Wang, Zhixin Qi, Lei Zheng, Yun Feng, Junfei Ouyang, Haoqi Zhang, Xiangxi Zhang, Ziming Shen, and Shirong Liu. 2020. April: An automatic graph data management system based on reinforcement learning. In Proceedings of the ACM International on Conference on Information and Knowledge Management. 3465–3468.
[76]
Michael J. Welch, Uri Schonfeld, Dan He, and Junghoo Cho. 2011. Topical semantics of Twitter links. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining. 327–336.
[77]
Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon. 2013. Overlapping community detection using seed set expansion. In Proceedings of the ACM International on Conference on Information and Knowledge Management. 2099–2108.
[78]
Kai Zheng, Han Su, Bolong Zheng, Shuo Shang, Jiajie Xu, Jiajun Liu, and Xiaofang Zhou. 2015. Interactive top-k spatial keyword queries. In Proceedings of the IEEE 31st International Conference on Data Engineering. IEEE, 423–434.
Index Terms
- Scalable Spatio-temporal Top-k Interaction Queries on Dynamic Communities
Recommendations
Scalable Spatio-Temporal Top-k Community Interactions Query
SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information SystemsThe excessive amount of data that online users produce through social media platforms provides valuable insights about users and communities at scale. Existing techniques have not fully exploited such data to help practitioners perform a deep analysis ...
Scalable and efficient processing of top-k multiple-type integrated queries
AbstractIn this paper, we define a new class of queries, the top-k multiple-type integrated query (simply, top-k MULTI query). It deals with multiple data types and finds the information in the order of relevance between the query and the object. Various ...
Probabilistic top-k and ranking-aggregate queries
Ranking and aggregation queries are widely used in data exploration, data analysis, and decision-making scenarios. While most of the currently proposed ranking and aggregation techniques focus on deterministic data, several emerging applications involve ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
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: 23 March 2024
Online AM: 16 February 2024
Accepted: 01 February 2024
Revised: 11 December 2023
Received: 01 March 2023
Published in TSAS Volume 10, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 179Total Downloads
- Downloads (Last 12 months)179
- Downloads (Last 6 weeks)4
Reflects downloads up to 29 Jan 2025
Other Metrics
Citations
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