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/