Dynamic Quotient Topology Model and Its Application to Optimal Path Finding
QI Ping1,2 , LI Long-Shu1
1.School of Computer Science and Technology, Anhui University, Hefei 230039 2.School of Mathematics and Computer Science, Tongling University, Tongling 244000
Abstract To settle the problem solving under dynamic conditions, according to the fact that the topological structure changes with time, the traditional theory of quotient space is extended by using the trust model in sociology for reference. Based on the creditability evaluation of nodes by Bayesian model, a kind of dynamic quotient topology model based on the trust mechanism is proposed, and then this model is applied to optimal path finding. Theoretical analysis and simulation results prove that the proposed model can efficiently enhance the path reliability and meet the requirement of dynamic problem solving with fewer time costs.
[1] Zhang B, Zhang L. Theory and Applications of Problem Solving. Amsterdam, the Netherlands: Elsevier, 1992 [2] Zhang L, Zhang B. The Quotient Space Theory of Problem Solving. Fundamenta Informaticae, 2004, 59(2/3): 287-298 [3] Zhang L, Zhang B. Theory of Fuzzy Quotient Space (Methods of Fuzzy Granular Computing). Journal of Software, 2003, 14(4): 770-776 (in Chinese) (张 铃,张 钹.模糊商空间理论(模糊粒度计算方法).软件学报, 2003, 14 (4): 770-776) [4] Zhang Y P, Zhang L, Wu T. The Representation of Different Gra-nular Worlds: A Quotient Space. Chinese Journal of Computers, 2004, 27(3): 328-333 (in Chinese) (张燕平,张 铃,吴 涛.不同粒度世界的描述法——商空间法.计算机学报, 2004, 27(3): 328-333) [5] Zhang L, He F Z, Zhang Y P, et al. A New Algorithm for Optimal Path Finding in Complex Networks Based on the Quotient Space. Fundamenta Informaticae, 2009, 93(4): 459-469 [6] He F G, Zhang Y P, Zhao S, et al. Computing the Point-to-Point Shortest Path: Quotient Space Theory's Application in Complex Network // Proc of the 5th International Conference on Rough Set and Knowledge Technology. Beijing, China, 2010: 751-758 [7] Zhang Y P, Xu X S, Hua B, et al. Contracting Community for Computing Maximum Flow // Proc of the IEEE International Conference on Granular Computing. Hangzhou, China, 2012: 773-778 [8] Chen J, Zhang Y P, Zhao S. A Structural Description: Ordered AND/OR Graph. Journal of Nanjing University: Natural Sciences, 2013, 49(2): 235-244 (in Chinese) (陈 洁,张燕平,赵 姝.一种结构化描述方法:保序性与或图.南京大学学报:自然科学版, 2013, 49(2): 235-244) [9] Zhang L, Zhang B. Dynamic Quotient Space Model and Its Basic Properties. Pattern Recognition and Artificial Intelligence, 2012, 25(2): 181-185 (in Chinese) (张 铃,张 钹.动态商空间模型及其基本性质.模式识别与人工智能, 2012, 25(2): 181-185) [10] Wang W, Zeng G S, Tang D Z, et al. Dynamic Trusted Scheduling for Cloud Computing. Expert Systems with Applications, 2012, 39(3): 2321-2329 [11] Jasang A, Ismail R. The Beta Reputation System[EB/OL]. [2012-10-01]. http://persons.unik.no/josang/papers/JI2002-Bled.pdf [12] Hecherman. A Tutorial on Learning with Bayesian Networks[EB/OL]. [2012-10-11]. http://ftp.research.microsoft.com/pub/tr/tr-95-06.pdf [13] Yin H Y, Xu L Q. Measuring the Structural Vulnerability of Road Network: A Network Efficiency Perspective. Journal of Shanghai Jiaotong University: English Edition, 2010, 15(6): 736-742 [14] Yin H Y, Xu L Q. A Model for Identifying Vulnerable Links of Road Networks Based on Bayesian Networks. Journal of Systems & Management, 2010, 19(6): 656-661 (in Chinese) (尹洪英,徐丽群.基于贝叶斯网络的路网脆弱路段识别模型.系统管理学报, 2010, 19(6): 656-661)
2014, Vol. 27 
