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
- 负责人:
- 金额:$ 24.79万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-03-15 至 2025-01-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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包括一个代表性不足的研究生在这项研究中。还将利用这一项目的技术和成果,为PI的机构开发教育和培训模块。因此,该项目将提高PI管辖区的科学研究、培训和教育能力。EPSCoR提案的目标是开发快速、可扩展的方法,用于挖掘和分析大型动态图。这样的图的示例包括社交网络、人类接触网络、web图和功能性大脑网络。该提案解决了基于子结构的问题,如寻找不断发展的社区和列举有趣的时间子图或图案在神经科学,生物信息学,基础设施和社会领域的应用。尽管静态图有丰富的文献,但动态图的文献还很新。现有的动态图的并行算法表现出有限的可扩展性,由于其计算到存储器操作的低比率和不规则的存储器访问模式。因此,这种算法表现出较弱的空间和时间局部性,导致缓存利用率低和通信量高。拟议的研究将利用与伯克利实验室性能和算法组的独特合作,利用最先进的用户设施和领先的专业知识来应对上述技术挑战。该提案旨在开发可扩展的并行方法,有效的负载平衡和通信避免技术,数据减少采样和稀疏化的方法,以及有效的形式化的时间度量。从这个建议产生的数学方法将适用于理解各种现实世界的系统的动态特性,例如,定位关键神经元在皮层(大脑)网络,路由规划的基础设施网络中的时变流量,建模疾病/病毒或信息传播的社会/接触网络。因此,该项目将扩大PI的研究能力,以构建有影响力的软件/技术工具,并提高他作为研究导师和教育者在其所在机构为多样化学生群体服务的能力。该奖项反映了NSF的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection
- DOI:10.1007/s41109-023-00592-1
- 发表时间:2023-09
- 期刊:
- 影响因子:2.2
- 作者:Naw Safrin Sattar;A. Buluç;Khaled Z. Ibrahim;S. Arifuzzaman
- 通讯作者:Naw Safrin Sattar;A. Buluç;Khaled Z. Ibrahim;S. Arifuzzaman
Fast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs
- DOI:10.1145/3605573.3605637
- 发表时间:2023-08
- 期刊:
- 影响因子:0
- 作者:M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;Cy Chan;J. Shalf;S. Arifuzzaman
- 通讯作者:M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;Cy Chan;J. Shalf;S. Arifuzzaman
Fast Community Detection in Graphs with Infomap Method using Accelerated Sparse Accumulation
- DOI:10.1109/ipdpsw59300.2023.00103
- 发表时间:2023-05
- 期刊:
- 影响因子:0
- 作者:M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;S. Arifuzzaman;Doru-Thom Popovici;J. Shalf;Cy Chan
- 通讯作者:M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;S. Arifuzzaman;Doru-Thom Popovici;J. Shalf;Cy Chan
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Shaikh Arifuzzaman其他文献
DyG-DPCD: A Distributed Parallel Community Detection Algorithm for Large-Scale Dynamic Graphs
- DOI:
10.1007/s10766-024-00780-1 - 发表时间:
2024-11-19 - 期刊:
- 影响因子:0.900
- 作者:
Naw Safrin Sattar;Khaled Z. Ibrahim;Aydin Buluc;Shaikh Arifuzzaman - 通讯作者:
Shaikh Arifuzzaman
Shaikh Arifuzzaman的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Shaikh Arifuzzaman', 18)}}的其他基金
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:大型动态图中演化模式挖掘和分析的快速算法
- 批准号:
2132212 - 财政年份:2022
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
相似海外基金
RII Track-4:NSF: Integrated Electrochemical-Optical Microscopy for High Throughput Screening of Electrocatalysts
RII Track-4:NSF:用于高通量筛选电催化剂的集成电化学光学显微镜
- 批准号:
2327025 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: Resistively-Detected Electron Spin Resonance in Multilayer Graphene
RII Track-4:NSF:多层石墨烯中电阻检测的电子自旋共振
- 批准号:
2327206 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: Improving subseasonal-to-seasonal forecasts of Central Pacific extreme hydrometeorological events and their impacts in Hawaii
RII Track-4:NSF:改进中太平洋极端水文气象事件的次季节到季节预报及其对夏威夷的影响
- 批准号:
2327232 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: Design of zeolite-encapsulated metal phthalocyanines catalysts enabled by insights from synchrotron-based X-ray techniques
RII Track-4:NSF:通过基于同步加速器的 X 射线技术的见解实现沸石封装金属酞菁催化剂的设计
- 批准号:
2327267 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: From the Ground Up to the Air Above Coastal Dunes: How Groundwater and Evaporation Affect the Mechanism of Wind Erosion
RII Track-4:NSF:从地面到沿海沙丘上方的空气:地下水和蒸发如何影响风蚀机制
- 批准号:
2327346 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: In-Situ/Operando Characterizations of Single Atom Catalysts for Clean Fuel Generation
RII Track-4:NSF:用于清洁燃料生成的单原子催化剂的原位/操作表征
- 批准号:
2327349 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4: NSF: Fundamental study on hydrogen flow in porous media during repetitive drainage-imbibition processes and upscaling for underground energy storage
RII Track-4:NSF:重复排水-自吸过程中多孔介质中氢气流动的基础研究以及地下储能的升级
- 批准号:
2327317 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: An Integrated Urban Meteorological and Building Stock Modeling Framework to Enhance City-level Building Energy Use Predictions
RII Track-4:NSF:综合城市气象和建筑群建模框架,以增强城市级建筑能源使用预测
- 批准号:
2327435 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4: NSF: Developing 3D Models of Live-Endothelial Cell Dynamics with Application Appropriate Validation
RII Track-4:NSF:开发活内皮细胞动力学的 3D 模型并进行适当的应用验证
- 批准号:
2327466 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant
RII Track-4:NSF: HEAL: Heterogeneity-aware Efficient and Adaptive Learning at Clusters and Edges
RII Track-4:NSF:HEAL:集群和边缘的异质性感知高效自适应学习
- 批准号:
2327452 - 财政年份:2024
- 资助金额:
$ 24.79万 - 项目类别:
Standard Grant