不确定图最小割边问题研究

Uncertain Graph Minimum Cut

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在。文中研究的是不确定图中最小割问题,也就是说:在不确定图中,由于数据的不确定性,当某边或者某顶点去掉时,可能造成最小割变化,而通常最为关心的则是这个最小割的最大值在不确定图中的概率是多少。

In recent years, large amounts of data generated in the various fields can be modeled as a graph structure naturally, such as protein interaction networks, social networks. Means of measurement inaccuracy and the nature of the data itself, lead to uncertainty prevalent in many chart data. This paper studies the problem that is uncertain minimum cut problem, that is to say ： in the uncertain figure, due to the uncertainty of the data, when one side or one vertex removed, minireal cut may be changed, and what is cared about is the maximum the minimum cut probability.