Balanced Hop-Constrained Path Enumeration in Signed Directed Graphs
Authors: 
Zhiyang Tang, Jinghao Wang, Yanping Wu, Xiaoyang Wang, Lu Qin, Ying ZhangAuthors Info & Claims
Pages 315 - 328
Abstract
Hop-constrained path enumeration, which aims to output all the paths from two distinct vertices within the given hops, is one of the fundamental tasks in graph analysis. Previous works about this problem mainly focus on unsigned graphs. Nevertheless, with the ever-growing popularity of online social media, signed graphs with positive and negative edges are becoming increasingly ubiquitous and there is a paucity of balanced paths (i.e., paths with an even number of negative edges) enumeration which makes more sense according to balance theory. Motivated by this, in this paper, we propose a new problem, i.e., enumerate balanced paths with hop constraint (BPHC). A baseline method firstly is proposed by extending the DFS method. To further speed up the efficiency, we construct an almost-satisfy table to instantly correct unbalanced state during the search process. Based on the almost-satisfy table, we develop algorithm BMAS by combining the shortest path length in the process of table update and lookup. We conduct experiments on four real world networks to verify the performance of the proposed algorithms.
References
[1]
Bernstein, A., Chechi, S.: Incremental topological sort and cycle detection in expected total time. In: SODA, pp. 21–34 (2018)
[2]
Chen, C., Wu, Y., Sun, R., Wang, X.: Maximum signed -clique identification in large signed graphs. IEEE Trans. Knowl. Data Eng. (2021)
[3]
Chen, S., Qian, H., Wu, Y., Chen, C., Wang, X.: Efficient adoption maximization in multi-layer social networks. In: ICDMW, pp. 56–60 (2019)
[4]
Derr, T., Ma, Y., Tang, J.: Signed graph convolutional networks. In: ICDM, pp. 929–934 (2018)
[5]
Gotthilf Z and Lewenstein M Improved algorithms for the k simple shortest paths and the replacement paths problems Inf. Process. Lett. 2009 109 7 352-355
[6]
Harary F On the notion of balance of a signed graph Mich. Math. J. 1953 2 2 143-146
[7]
Hershberger, J., Maxel, M., Suri, S.: Finding the k shortest simple paths: a new algorithm and its implementation. TALG 3(4) (2007)
[8]
Kumar R and Calders T 2SCENT: an efficient algorithm to enumerate all simple temporal cycles PVLDB 2018 11 11 1441-1453
[9]
Lai, Z., Peng, Y., Yang, S., Lin, X., Zhang, W.: PEFP: efficient k-hop constrained ST simple path enumeration on FPGA. In: ICDE, pp. 1320–1331 (2021)
[10]
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: WWW, pp. 641–650 (2010)
[11]
Peng Y, Zhang Y, Lin X, Zhang W, Qin L, and Zhou J Hop-constrained ST simple path enumeration: towards bridging theory and practice PVLDB 2019 13 4 463-476
[12]
Sun, R., Chen, C., Wang, X., Zhang, W., Zhang, Y., Lin, X.: Efficient maximum signed biclique identification. In: ICDE, pp. 1313–1325 (2023)
[13]
Sun R, Chen C, Wang X, Zhang Y, and Wang X Stable community detection in signed social networks IEEE Trans. Knowl. Data Eng. 2020 34 10 5051-5055
[14]
Sun, R., Wu, Y., Chen, C., Wang, X., Zhang, W., Lin, X.: Maximal balanced signed biclique enumeration in signed bipartite graphs. In: ICDE, pp. 1887–1899 (2022)
[15]
Sun, R., Wu, Y., Wang, X.: Diversified top- community search in geo-social network: a k-truss based model. In: EDBT (2022)
[16]
Sun, R., Wu, Y., Wang, X., Chen, C., Zhang, W., Lin, X.: Clique identification in signed graphs: a balance theory based model. IEEE Trans. Knowl. Data Eng. (2023)
[17]
Sun, S., Chen, Y., He, B., Hooi, B.: Pathenum: towards real-time hop-constrained ST path enumeration. In: SIGMOD, pp. 1758–1770 (2021)
[18]
Tang, J., Aggarwal, C., Liu, H.: Recommendations in signed social networks. In: WWW, pp. 31–40 (2016)
[19]
Wang X, Zhang Y, Zhang W, Lin X, and Chen C Bring order into the samples: a novel scalable method for influence maximization IEEE Trans. Knowl. Data Eng. 2016 29 2 243-256
[20]
Wu, Y., Sun, R., Chen, C., Wang, X., Fu, X.: Efficiently answering minimum reachable label set queries in edge-labeled graphs. In: CIKM, pp. 4585–4589 (2022)
[21]
Wu, Y., Sun, R., Chen, C., Wang, X., Zhu, Q.: Maximum signed (k, r)-truss identification in signed networks. In: CIKM, pp. 3337–3340 (2020)
[22]
Wu Y, Zhao J, Sun R, Chen C, and Wang X Efficient personalized influential community search in large networks Data Sci. Eng. 2021 6 3 310-322
[23]
Zhang, C., Zhang, Y., Zhang, W., Lin, X., Cheema, M.A., Wang, X.: Diversified spatial keyword search on road networks. In: EDBT (2014)
[24]
Zhang, J., Yang, S., Ouyang, D., Zhang, F., Lin, X., Yuan, L.: Hop-constrained ST simple path enumeration on large dynamic graphs. In: ICDE, pp. 762–775 (2023)
[25]
Zhang X, Wang H, Yu J, Chen C, Wang X, and Zhang W Polarity-based graph neural network for sign prediction in signed bipartite graphs World Wide Web 2022 25 2 471-487
Recommendations
Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs
Web Information Systems Engineering – WISE 2022AbstractHop-constrained s-t simple path () enumeration is a fundamental problem in graph analysis. Existing solutions for this problem focus on unlabelled graphs and assume queries are issued without any label constraints. However, in many real-...
Hop-Constrained s-t Simple Path Enumeration in Large Uncertain Graphs
Databases Theory and ApplicationsAbstractUncertain graphs are graphs where each edge is assigned with a probability of existence. In this paper, we study the problem of hop-constrained s-t simple path enumeration in large uncertain graphs. To the best of our knowledge, we are the first ...
Balanced paths in acyclic networks: Tractable cases and related approaches
Given a weighted acyclic network G and two nodes s and t in G, we consider the problem of computing k balanced paths from s to t, that is, k paths such that the difference in cost between the longest and the shortest path is minimized. The problem has ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Nov 2023
391 pages
ISBN:978-3-031-47842-0
DOI:10.1007/978-3-031-47843-7
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 07 November 2023
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
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