Credible Nearest Neighbor Query in Uncertain Network
GUO Changyou①② ZHENG Xuefeng① GAO Xiulian②
①(School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China) ②(Dezhou University, Dezhou 253000, China)
Uncertain factors are a common phenomenon in the real world; therefore, it is very meaningful to study on the trusted neighbor query under uncertain network conditions. This paper puts forwards a new solution. The uncertain network is modeled as uncertain weighed graph, and these definitions of the uncertain graph are given, such as sample graph, sample graph index, base network, length of feasible path and expected length of feasible path. Based on these the high-efficiency credible neighbor query algorithm for uncertain graph is put forward under constraint conditions. This algorithm is transforms the issue of neighbor query in the uncertain network equivalently to the issue of neighbor query in the base network. The theoretic analysis and experimental results show that the credible neighbor query algorithm proposed in the paper can solve the neighbor query problem in the environment of the uncertain network from non-deterministic perspective.
LUO L, WU W J, and ZHANG F. Energy modeling based on clouddata center[J]. Journal of Software, 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki.jos.004604.
YIN Bo, WANG Ying, QIU Xuesong, et al. A resource provisioning mechanism for service providers in cloud[J]. Journal of Electronics & Information Technology, 2014, 36(1): 15-21. doi: 10.3724/SP.J.1146.2013.00427.
ZHANG Haijie, JIANG Shouxu, and ZOU Zhaonian. An efficient algorithm for top-k proximity query on uncertain graph[J]. Chinese Journal of Computers, 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885.
GAO Jun and HAO Zhongxiao. Credible nearest neighbor query in constraint fuzzy network[J]. Computer Engineering, 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01. 010.
[5]
LIU B. Uncertainty Theory[M]. 2nd ed., Berlin: Springer- Verlag, 2007, Chapter 1-Chapter 2 .
[6]
LIU B. Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty[M]. Berlin: Springer-Verlag, 2010, Chapter 1-Chapter 2.
[7]
LIU B. Uncertainty distribution and independence of uncertain processes[J]. Fuzzy Optimization and Decision Making, 2014, 13(3): 259-271. doi: 10.1007/s10700-014- 9181-5.
[8]
ZHOU J, CHEN L, and WANG K. Path optimality conditions for minimum spanning tree problem with uncertain edge weights[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2015, 23(1): 49-71. doi: 10.1142/s0218488515500038.
[9]
GAO X L. Uncertain relations on a finite set and their properties[J]. Pure and Applied Mathematics Journal, 2014, 3(1): 13-19. doi: 10.11648/j.pamj.s.20140301.13.
[10]
GAO X L. Tree index of uncertain graphs[J]. Soft Computing, 2015. doi: 10.1007/s00500-015-1597-5.
[11]
GAO X L and GAO Y. Connectedness index of uncertainty graphs[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2013, 21(1): 127-137. doi: 10.1142/S0218488513500074.
[12]
GAO X L. Regularity index of uncertain graph[J]. Journal of Intelligent & Fuzzy Systems, 2014, 27(4): 1671-1678. doi: 10.3233/IFS-141133.
[13]
DING S B. Uncertain minimum cost flow problem[J]. Soft Computing, 2014, 18(11): 2201-2207. doi: 10.1007/s00500- 013-1194-4.
[14]
Gao X, Gao Y, and Ralescu D. On Liu’s inference rule for uncertain systems[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2010, 18(1): 1-11. doi: 10.1142/S0218488510006349.
[15]
Gao Y, Yang L X, et al. On distribution function of the diameter in uncertain graph[J]. Information Sciences, 2015, 296(1): 61-74. doi: 10.1016/j.ins.2014.10.048.
[16]
GAO Y. Shortest path problem with uncertain arc lengths[J]. Computers and Mathematics with Applications, 2011, 62(6): 2591-2600. doi: 10.1016/j.camwa.2011.07.058.
[17]
LIU B. Some research problems in uncertainty theory[J]. Journal of Uncertain Systems, 2009, 3(1): 3-10.