RII Track-4:NSF: DyG-MAP: Fast Algorithms for Mining and Analysis of Evolving Patterns in Large Dynamic Graphs

RII Track-4：NSF：DyG-MAP：大型动态图中演化模式挖掘和分析的快速算法

• 批准号: 2323533
• 负责人: Shaikh Arifuzzaman
• 金额: $ 24.79万
• 依托单位: University of Nevada Las Vegas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-03-15 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2323533&HistoricalAwards=false
• 关键词: RII; Track; NSF; DyG; MAP

Graphs (networks) are a versatile scientific framework to represent and analyze biological, social, and human-made complex systems. Such complex systems are inherently dynamic—for example, social interactions and human activities are intermittent; links appear and disappear in functional brain networks. Despite “time” playing a central role in those systems, most of the classic studies on graphs are based on the topological properties of static graphs (graphs that do not change over time). The existing works on dynamic graphs show only limited scalability for large-scale practical datasets. This proposed research aims at designing fast, scalable methods for revealing dynamic behaviors of a socio-technical system by developing innovative algorithmic and computing techniques. The host site, Berkeley Lab, will provide unique expertise and mentoring and facilitate access to leading supercomputer facilities to achieve the proposed research goals. The project will generate new algorithmic techniques and scalable software tools to advance graph-based data science and high-performance scientific computing. The PI includes an underrepresented graduate student in this research. Educational and training modules will also be developed for PI’s institution from the techniques and results emerging from this project. Thus, the project will enhance the scientific research, training, and education capacity of the PI’s jurisdiction.The goal of this EPSCoR proposal is to develop fast and scalable methods for mining and analyzing large dynamic graphs. Examples of such graphs include social networks, human contact networks, web graphs, and functional brain networks. The proposal addresses substructure-based problems such as finding evolving communities and enumerating interesting temporal subgraphs or motifs with applications in neuroscience, bioinformatics, infrastructure, and social domains. Even though there exists a rich literature for static graphs, the literature for dynamic graphs is very nascent. Existing parallel algorithms for dynamic graphs demonstrate limited scalability due to their low ratio of compute to memory operations and the irregular memory access patterns. Consequently, such algorithms show weak spatial and temporal locality, leading to poor cache utilization and high communication volume. The proposed research will utilize a unique collaboration with the Performance and Algorithms Group of Berkeley Lab to avail the most advanced user facilities and leading expertise to tackle the above technical challenges. The proposal aims at developing scalable parallel methods with efficient load-balancing and communication-avoidance techniques, data reduction approaches with sampling and sparsification, and efficient formalization of temporal metrics. Algorithmic methods generated from this proposal will be applicable in understanding dynamic properties of various real-world systems—for instance, locating key neurons in cortical (brain) networks, route-planning for time-varying traffic in infrastructure networks, modeling disease/virus or information propagation in social/contact networks. Therefore, the project will expand the PI’s research capacity to build impactful software/technology tools and also enhance his ability to serve a diverse student population at his host institution as both a research mentor and an educator.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图形（网络）是一种通用的科学框架，用于表示和分析生物、社会和人造的复杂系统，这些复杂系统本质上是动态的——例如，社会互动和人类活动在功能性大脑网络中出现和消失。尽管“时间”在这些系统中发挥着核心作用，但大多数关于图的经典研究都是基于静态图（不随时间变化的图）的拓扑特性，现有的动态图研究仅显示出有限的可扩展性。 -规模实用这项拟议的研究旨在通过开发创新的算法和计算技术来设计快速、可扩展的方法来揭示社会技术系统的动态行为，伯克利实验室将提供独特的专业知识和指导，并促进使用领先的超级计算机设施。为了实现拟议的研究目标，该项目将产生新的算法技术和可扩展的软件工具，以推进基于图形的数据科学和高性能科学计算。该研究还将包括一名代表性不足的研究生。发达因此，该项目将增强 PI 管辖范围内的科学研究、培训和教育能力。该 EPSCoR 提案的目标是开发快速且可扩展的挖掘和分析方法。此类图的示例包括社交网络、人类联系网络、网络图和功能性大脑网络。该提案解决了基于子结构的问题，例如寻找不断发展的社区和枚举有趣的时间子图或主题及其应用。尽管存在丰富的静态图文献，但动态图的现有并行算法由于计算与内存操作的比率较低而表现出有限的可扩展性。经过测试，此类算法表现出较弱的空间和时间局部性，导致缓存利用率低且通信量大。本研究将利用与伯克利实验室性能和算法小组的独特合作来利用最先进的用户。该提案旨在开发具有高效负载平衡和通信避免技术的可扩展并行方法、具有采样和稀疏化的数据缩减方法以及由此生成的时间度量的有效形式化方法。该提案将适用于理解各种现实世界系统的动态特性，例如，定位皮质（大脑）网络中的关键神经元、基础设施网络中随时间变化的流量的路线规划、对疾病/病毒或信息传播进行建模因此，该项目将扩大 PI 的研究能力，以构建有影响力的软件/技术工具，并增强他作为研究导师和教育者为所在机构的多元化学生群体提供服务的能力。该奖项反映了 NSF 的贡献。法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection

探索时间社区演化：动态社区检测的算法方法和并行优化

• DOI: 10.1007/s41109-023-00592-1
• 发表时间: 2023-09-18
• 期刊: Applied Network Science
• 影响因子: 2.2
• 作者: Naw Safrin Sattar;A. Buluç;Khaled Z. Ibrahim;S. Arifuzzaman
• 通讯作者: S. Arifuzzaman

Fast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs

大图中基于 K-truss 的高效局部社区检测的快速并行索引构建

• DOI: 10.1145/3605573.3605637
• 发表时间: 2023-08-07
• 期刊: Proceedings of the 52nd International Conference on Parallel Processing
• 作者: M. A. M. Faysal;Maximilian H. Bremer;Cy Chan;J. Shalf;S. Arifuzzaman
• 通讯作者: S. Arifuzzaman

Fast Community Detection in Graphs with Infomap Method using Accelerated Sparse Accumulation

使用加速稀疏累积的 Infomap 方法在图中进行快速社区检测

• DOI: 10.1109/ipdpsw59300.2023.00103
• 发表时间: 2023-05-01
• 期刊: 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
• 作者: M. A. M. Faysal;Maximilian H. Bremer;S. Arifuzzaman;Doru;J. Shalf;Cy Chan
• 通讯作者: Cy Chan