Querying and Mining Dynamics in Evolving Graphs and Networks

演化图和网络中的查询和挖掘动态

• 批准号: RGPIN-2020-04506
• 负责人: Pei, Jian
• 金额: $ 4.66万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750572
• 关键词: Querying; Mining; Dynamics; Evolving; Graphs

In many applications, huge amounts of complex data are modeled as graphs or networks. More often than not, such graphs and networks are evolving all the time, such as interactions in social networks and traffics in geographical networks/communication networks. Analyzing and mining evolving graphs and networks enable us to understand sophisticated behaviors that cannot be captured comprehensively in the past. Dynamics are a beauty in evolving graphs and networks. Analyzing and making good use of dynamics in evolving graphs and networks provide us unprecedented power to conquer big data, and, at the same time, post grand technical challenges. This proposed research program is to embrace the opportunities and address the technical challenges in a timely and practical manner. We will design practical and principled analytics tasks and develop efficient and effective methods. Specifically, we will identify a series of novel tasks that are practically useful to capture dynamics in evolving graphs and networks and, at the same time, are computationally feasible or approximate-able. Those tasks include both data statistics queries and machine learning tasks. Second, we will develop principled algorithmic approaches and data structures that are effective and efficient for those target tasks. Third, we will build a big graph and network data system as a platform to integrate our algorithmic inventions, and conduct case studies in real application scenarios to verify and evaluate our research development and produce practical impact. This proposed research program continues my long-term endeavor to conquer massive sophisticated data. The ultimate objective is to develop business intelligence based on dynamic graph and network data, and train HQP equipped with the up-to-date knowledge and skills and capable of producing innovations in industry and academia. We divide the proposed research program into three projects. First, we will study how to model dynamics in not-evolving networks with various constraints and preferences. Second, we will investigate methods analyzing and mining dynamics in evolving networks. Last, we will build a distributed big graph data system for analyzing and mining dynamics in evolving networks. We will build a distributed graph big data system as a platform to integrate our algorithmic inventions and focus on scalability using cloud computing.  The proposed research program will systematically investigate a series of novel research problems and lead to fruitful publications in premier academic venues. The research outcome will advance the frontier in this fast-growing area and produce substantial impact in academia. HQP will be trained in the program to meet the deadly demand from both academia and industry in this area. We will invite our industry partners to test drive the outcome in this proposed research. Some techniques and some components of the graph database system may likely be adopted by some partners.

在许多应用中，大量复杂的数据被建模为图形或网络。通常情况下，这种图和网络一直在发展，例如社交网络中的交互和地理网络/通信网络中的流量。分析和挖掘不断发展的图形和网络使我们能够理解过去无法全面捕获的复杂行为。动态是进化图和网络中的一种美。分析和充分利用不断发展的图和网络中的动态，为我们提供了前所未有的力量来征服大数据，同时也提出了巨大的技术挑战。这项拟议的研究计划旨在及时、实用地抓住机遇并解决技术挑战。我们将设计实用和有原则的分析任务，并开发高效和有效的方法。具体来说，我们将确定一系列新的任务，这些任务对于捕获不断发展的图和网络中的动态特性实际上是有用的，同时在计算上是可行的或近似的。这些任务包括数据统计查询和机器学习任务。其次，我们将开发原则性的算法方法和数据结构，这些算法和数据结构对这些目标任务是有效和高效的。第三，我们将构建大图和网络数据系统作为平台，整合我们的算法发明，并在真实的应用场景中进行案例研究，以验证和评估我们的研究开发并产生实际影响。这项研究计划延续了我长期以来征服大量复杂数据的奋进。最终目标是开发基于动态图和网络数据的商业智能，并培养具备最新知识和技能的HQP，并能够在工业和学术界进行创新。我们将研究计划分为三个项目：第一，我们将研究如何在具有各种约束和偏好的非进化网络中建模动态;第二，我们将研究分析和挖掘进化网络中动态的方法。最后，我们将构建一个分布式大图数据系统，用于分析和挖掘不断发展的网络中的动态。我们将建立一个分布式图大数据系统作为平台，以整合我们的算法发明，并专注于使用云计算的可扩展性。拟议的研究计划将系统地研究一系列新的研究问题，并在一流的学术场所发表富有成果的论文。研究成果将推进这一快速发展领域的前沿，并在学术界产生重大影响。HQP将在该项目中接受培训，以满足学术界和工业界在这一领域的迫切需求。我们将邀请我们的行业合作伙伴来测试这项拟议研究的成果。图形数据库系统的某些技术和某些组件可能会被某些合作伙伴采用。