Querying and Mining Dynamics in Evolving Graphs and Networks

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

• 批准号: RGPIN-2020-04506
• 负责人: Pei, Jian
• 金额: $ 4.66万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=717043
• 关键词: 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将在该计划中接受培训，以满足学术界和工业界在这一领域的致命需求。我们将邀请我们的行业合作伙伴在这项拟议的研究中测试推动结果。图形数据库系统的一些技术和一些组件可能会被一些合作伙伴采用。