|
|
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) |
|
|
Abstract 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.
|
Received: 23 June 2015
Published: 22 January 2016
|
|
Fund: The National Natural Science Foundation of China (61163025), The Project of Beijing Key Laboratory of Knowledge Engineering for Materials Science (Z121101002812005) |
Corresponding Authors:
GUO Changyou
E-mail: guochangyouustb@139.com
|
|
|
|
[1] |
罗亮, 吴文峻, 张飞. 面向云计算数据中心的能耗建模方法[J]. 软件学报, 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki. jos.004604.
|
|
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.
|
[2] |
殷波, 王颖, 邱雪松, 等. 一种面向云服务提供商的资源分配机制[J]. 电子与信息学报, 2014, 36(1): 15-21. doi: 10.3724/ SP.J.1146.2013.00427.
|
|
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.
|
[3] |
张海杰, 姜守旭, 邹兆年. 不确定图上的高效top-k近邻查询处理算法[J]. 计算机学报, 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885.
|
|
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.
|
[4] |
高峻, 郝忠孝. 受限模糊网络可信近邻查询[J]. 计算机工程, 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01.010.
|
|
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.
|
|
|
|