不确定图最小生成树算法

Minimum spanning tree on uncertain graphs

很多领域产生的大量数据都可以很自然地用不确定图模型表示和描述,如蛋白质交互网络、社交网络、无线传感器网络等。本文研究不确定图上最可靠的最小生成树问题,该问题具有广泛的应用价值和研究意义。精确地求解算法需要枚举所有可能的最小生成树并找出其中出现次数最多的那个。因此,枚举开销随着边数增多呈指数增长,当图规模较大时并不可行。为此本文提出了一个时间复杂度为O(d|V|~2)的启发式贪心算法,其中d为最大的顶点度数,|V|为顶点数。实验结果表明,该算法具有较好的效率和较高扩展性。

In recent years,lots of data in various domain can be represented and described by uncertain graph model,e.g. protein interaction networks,social networks,wireless sensor networks,etc. This paper investigates the most reliable minimum spanning tree on uncertain graph model,which has wide applications and research significance. The accurate algorithm enumerates all possible minimum spanning trees and find the most frequent one,the enumeration cost increases exponentially as the edge grows,which cannot fit the large graph computation. A heuristic greedy algorithm in O( d | v|~2) was proposed to solve the problem,where d is the largest degree,and |V| is the number of vertexes. Experimental results show that the algorithm is both efficient and scalable.