III: Small: Managing and Mining Uncertain Graphs

III：小：管理和挖掘不确定图

• 批准号: 1320542
• 负责人: George Kollios
• 金额: $ 50万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320542&HistoricalAwards=false
• 关键词: III; Small; Managing; Mining; Uncertain

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/

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