III: Small: Managing and Mining Uncertain Graphs

网络和图数据出现在许多不同的应用中，如社交网络、生物网络和移动自组织网络。在许多情况下，由于数据收集过程或数据的预处理，在可用的图表数据中存在固有的不确定性。此外，不确定或不准确的信息成为理解和有效利用这类图表中所含信息的严重障碍。在这个项目中，我们解决了管理和挖掘这类不确定图的问题。为此，我们将可能世界语义学应用于概率图和不确定图，并在此框架内研究了已建立的数据挖掘问题的算法。受现实生活应用程序的激励，我们专注于特定的数据分析任务。然而，我们使我们的框架足够通用，以便它可以用于广泛的任务和应用程序。特别是，我们开发了可扩展和高效的算法和方法来处理一些重要的任务，包括最近邻检索、聚类和划分、寻找重要的节点和边以及总结大型不确定图。我们预计这个项目的结果将对几个应用领域产生影响。例如，它们可以帮助基于互联网和社交媒体的公司分析他们的数据，并改进他们的定向广告政策和做法。这将为这些公司的生存创造机会，并帮助基于互联网的商业经济。在医学、生物和生物化学中，网络扮演着非常重要的角色，其中许多网络可以更好地建模为不确定网络。我们的项目可以帮助分析这些网络，并带来新的生物学见解。这个项目的结果传播如下：(1)我们开发公开可用的原型；(2)我们在课堂/讲座中介绍我们的工作成果；(3)我们通过出版物和演示将我们的结果传达给计算机科学和其他领域的科学家和我们的行业合作者。我们还积极尝试参与我们的研究生和本科生的研究，包括妇女和少数民族。有关更多信息，请访问网站：http://www.cs.bu.edu/~gkollios/ugraphs/

Network and graph data appear in many diverse applications such as social networks, biological networks, and mobile ad-hoc networks. In many cases, there is an inherent uncertainty in the available graph data either due to the data collection process or the preprocessing of the data. Furthermore, uncertainty or imprecise information becomes a critical impediment to understanding and effectively utilizing the information contained in such graphs. In this project, we address the problem of managing and mining such uncertain graphs. To do that, we adopt the possible-world semantics to probabilistic and uncertain graphs and within this framework we study algorithms for well-established data-mining problems. Motivated by real-life applications, we focus on specific data-analysis tasks. However, we make our framework general enough so that it can be used for a wide set of tasks and applications. In particular, we develop scalable and efficient algorithms and approaches to address a number of important tasks including nearest neighbor retrieval, clustering and partitioning, finding important nodes and edges, and summarizing large uncertain graphs. We expect the results of this project to have an impact on several application domains. For example, they can help internet-based and social-media related companies to analyze their data and improve their targeting advertisement policies and practices. This will create opportunities for making these companies viable and help the economy of internet-based business. In medicine, biology and biochemistry, networks play a very important role and many of these networks can be better modeled as uncertain networks. Our project can help analyze these networks and lead to new biological insights. The results of this project are disseminated as follows: (1) we develop publicly available prototypes; (2) we include the results of our work in our classes/lectures; (3) we communicate our results to scientists of computer science and other fields and our industry collaborators through publications and demos. We also actively try to engage in our research graduate and undergraduate students, including women and minorities.For further information see the web site at: http://www.cs.bu.edu/~gkollios/ugraphs/