An Efficient Keywords Search in Temporal Social Networks
Open Access
- 9 September 2023
- journal article
- research article
- Published by Springer Nature in Data Science and Engineering
- Vol. 8 (4) , 368-384
Abstract
With the increasing of requirements from many aspects, various queries and analyses arise focusing on social network. Time is a common and necessary dimension in various types of social networks. Social networks with time information are called temporal social networks, in which time information can be the time when a user sends message to another user. Keywords search in temporal social networks consists of finding relationships between a group users that has a set of query labels and is valid within the query time interval. It provides assistance in social network analysis, classification of social network users, community detection, etc. However, the existing methods have limitations in solving temporal social network keyword search problems. We propose a basic algorithm, the discrete timestamp algorithm, with the intention of turning the problem into a traditional keyword search on social networks. We also propose an approximative algorithm based on the discrete timestamp algorithm, but it still suffers from the traditional algorithms’ low efficiency. To further improve the performance, we propose a new algorithm based on dynamic programming to solve the keyword search in temporal social network. The main idea is to extend a vertex into a solution by edge-growth operation and tree-merger operation. We also propose two powerful pruning techniques to reduce the intermediate results during the extension. Additionally, all of the algorithms we proposed are capable of handling a variety of ranking functions, and all of them can be made to conform to top-N keyword querying. The efficiency and effectiveness of the proposed algorithms are verified through extensive empirical studies.Keywords
All Related Versions
Funding Information
- National Nature Science Foundation of China (61572537, U1501252)
This publication has 31 references indexed in Scilit:
- Efficient and Progressive Group Steiner Tree Search2016
- Towards Efficient Query Processing on Massive Time-Evolving Graphs2012
- BLINKS2007
- Spark2007
- Efficient IR-Style Keyword Search over Relational Databases2003
- Keyword searching and browsing in databases using BANKS2002
- The TSQL2 Data Model1995
- Beyond Steiner's problem: A VLSI oriented generalization1990
- The temporal query language TQuelACM Transactions on Database Systems, 1987
- The steiner problem in graphsNetworks, 1971