Probabilistic Path Queries in Path Networks: An Effective and Efficient Clustering Methods
DOI:
https://doi.org/10.53555/nncse.v2i3.477Keywords:
Clustering, probabilistic graphs correlated, algorithmAbstract
Efficiently processing shortest path (SP) queries over stochastic networks attracted a lot of research attention as such queries are very popular in the emerging real world applications such as Intelligent Transportation Systems and communication networks whose edge weights can be modeled as a random variable. Some pervious works aim at finding the most likely SP (the path with largest probability to be SP), and others search the least-expected-weight path. In all these works, the definitions of the shortest path query are based on simple probabilistic models which can be converted into the multi-objective optimal issues on a weighted graph. Challenging problem, two algorithms, the PEEDR and the CPGS clustering algorithm. Reliable clusters are those which are not likely to be disconnected in the context of different instantiations of the uncertain graph. we provide a generalized reliability measurement from two basic intuitions (purity and size balance) to overcome the challenges from standard reliability criterion, and develop a novel k-means algorithm to solve the uncertain clustering problem.
References
[1] Yu Gu, Member, Chunpeng Gao, Gao Cong, and Ge Yu, VOL. 26, Effective and Efficient Clustering Methods for Correlated Probabilistic GraphsNO. 5, May 2014.
[2] R. Jin, L. Liu, B. Ding, and H. Wang, “Distance-constraint reachability computation in uncertain graphs,” PVLDB, vol. 4, no. 9, pp. 551–562, Jun. 2011.
C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, New York, NY, USA: Springer, 2010.
M. Potamias, F. Bonchi, A. Gionis, and G. Kollios, “K-nearest neighbors in uncertain graphs,” PVLDB, vol. 3, no. 1, pp. 997–1008, Sept. 2010.
X. Lian and L. Chen, “A generic framework for handling uncertain data with local correlations,” PVLDB, vol. 4, no. 1, pp. 12–21, 2010.
P. Sen and A. Deshpande, “Representing and querying correlated tuples in probabilistic databases,” in Proc. ICDE, Istanbul, Turkey, 2007, pp. 596–605.
A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: A review,” ACM Comput. Surv., vol. 31, no. 3, pp. 264–323, Sept. 1999.
G. Kollios, M. Potamias, and E. Terzi, “Clustering large probabilistic graphs,”IEEE Trans. Knowl. Data Eng., vol. 25, no. 2, pp. 325–336,
Feb. 2013.R. Kannan,S. Vempala, and A. Vetta, “On clusterings: Good, bad and spectral,” J. ACM, vol. 51, no. 3, pp. 497–515, 2004.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
