III: Small: Collaborative Research: Cost-Efficient Sampling and Estimation from Large-Scale Networks

III:小型:协作研究:大规模网络的经济高效采样和估计

基本信息

  • 批准号:
    2209921
  • 负责人:
  • 金额:
    $ 25万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-11-15 至 2024-09-30
  • 项目状态:
    已结题

项目摘要

Sampling and estimating structural information from large-scale networks or graphs has been central to our understanding of the network dynamics and its rich set of applications. Markov Chain Monte Carlo (MCMC) has been the key enabler for a broader context of graph sampling, including estimating the properties of large graphs, sampling the corpus of documents indexed by search engines, sampling records from hidden databases behind Web forms, identifying subgraphs of certain characteristics and frequent graph pattern matching. Despite versatile applications of the MCMC methods and their customized algorithms for analyzing graph-structured data in various forms, there still exist critical challenges and limitations in the literature centered around the MCMC methods. One is the 'cost' consumption/constraints associated with the sampling operation, which limits the size of total samples obtained and negatively affects the accuracy of any estimator based on the obtained samples. Another limitation is that the recent advances in MCMC, especially built up on favorable non-reversible Markov chains, cannot be leveraged to the various large-graph sampling tasks, due to their required global knowledge of the underlying state space, lack of distribution implementation, unconstrained state space, as well as the simplified cost assumption. The goal of this research is to fully exploit the potentials of a set of crawling samplers by making the samplers adaptive and possibly interactive on a properly constructed graph domain, to transcend the current status-quo in the wide range of graph sampling tasks. Specifically, the project aims to: (i) build a theoretical framework to construct a suite of cost-efficient sampling policies by optimally balancing the tradeoff between the sample quality and quantity under challenged access environments with a given cost budget, (ii) design a class of adaptive random walks by fully exploiting the past information to achieve minimal temporal correlations over the obtained samples and by controlling the random walks collectively to enable maximal space exploration, and (iii) extend the standard MCMC toolkits toward faster and more cost-efficient exploration of feasible subgraphs/configurations and computing/optimization on a graph, along with extensive validations to create practical and usable solutions in reality. This research has a high potential impact on a vast range of multi-disciplinary applications, including sampling large-scale graphs for statistical inference and efficient estimation and randomized algorithms for combinatorial optimizations in various disciplines, where the standard MCMC methods have been dominant but also constrained our understanding.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.
从大规模网络或图中采样和估计结构信息一直是我们理解网络动力学及其丰富应用的核心。马尔可夫链蒙特卡罗(MCMC)已经成为一个更广泛的背景下的图采样,包括估计大图的属性,采样的语料库的文件索引的搜索引擎,采样记录从隐藏的数据库背后的Web表单,确定某些特征的子图和频繁的图形模式匹配的关键使能器。尽管MCMC方法及其定制算法在分析各种形式的图结构数据中的应用广泛,但在以MCMC方法为中心的文献中仍然存在关键的挑战和限制。一个是与采样操作相关联的“成本”消耗/约束,其限制了所获得的总样本的大小,并且对基于所获得的样本的任何估计器的准确性产生负面影响。另一个限制是MCMC的最新进展,特别是建立在有利的不可逆马尔可夫链上的进展,不能用于各种大型图采样任务,因为它们需要底层状态空间的全局知识,缺乏分布实现,不受约束的状态空间,以及简化的成本假设。本研究的目标是充分利用一组爬行采样器的潜力,使采样器的自适应和可能的互动上一个正确构建的图形域,超越目前的现状,在广泛的图形采样任务。具体而言,该项目旨在:(i)建立一个理论框架,通过在给定成本预算的情况下,在有挑战性的访问环境下最佳地平衡样本质量和数量之间的权衡,来构建一套具有成本效益的采样政策,(二)通过充分利用过去的信息,设计一类自适应随机游动,以在所获得的样本上实现最小的时间相关性,并通过控制随机游动,共同实现最大的空间探索,以及(iii)扩展标准MCMC工具包,以更快和更具成本效益地探索可行的子图/配置和图上的计算/优化,沿着广泛的验证,以在现实中创建实用和可用的解决方案。这项研究对广泛的多学科应用具有很高的潜在影响,包括用于统计推断和有效估计的大规模图采样以及用于各学科组合优化的随机算法,该奖项反映了NSF的法定使命,并被认为值得通过使用基金会的学术价值和更广泛的影响审查标准。

项目成果

期刊论文数量(6)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Characterizing the Efficiency of Graph Neural Network Frameworks with a Magnifying Glass
GRAFICS: Graph Embedding-based Floor Identification Using Crowdsourced RF Signals
FIS-ONE: Floor Identification System with One Label for Crowdsourced RF Signals
Controlling Epidemic Spread Under Immunization Delay Constraints
在免疫延迟限制下控制疫情蔓延
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Li, Shiju;Huang, Xin;Lee, Chul-Ho Lee;Eun, Do Young
  • 通讯作者:
    Eun, Do Young
Semi-supervised Learning with Network Embedding on Ambient RF Signals for Geofencing Services
  • DOI:
    10.1109/icde55515.2023.00208
  • 发表时间:
    2022-10
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Weipeng Zhuo;Kaili Chiu;Jierun Chen;Jiajie Tan;Edmund Sumpena;Shueng-Han Gary Chan;Sangtae Ha
  • 通讯作者:
    Weipeng Zhuo;Kaili Chiu;Jierun Chen;Jiajie Tan;Edmund Sumpena;Shueng-Han Gary Chan;Sangtae Ha
{{ 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 }}

Chul-Ho Lee其他文献

Melted insulator state under pressure in layered structured (Eu3-nSrn)Bi2S4F4
层状结构 (Eu3-nSrn)Bi2S4F4 中绝缘体在压力下的熔化状态
  • DOI:
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Bosen Wang;Kazuyuki Matsubayashi;Jinguang Cheng;Chul-Ho Lee;Yoshiya Uwatoko
  • 通讯作者:
    Yoshiya Uwatoko
Anti-proteolytic regulation of KRAS by USP9X/NDRG3 in KRAS-driven cancer development
USP9X/NDRG3 对 KRAS 的抗蛋白水解调节在 KRAS 驱动的癌症发展中
  • DOI:
    10.1038/s41467-024-54476-8
  • 发表时间:
    2025-01-16
  • 期刊:
  • 影响因子:
    15.700
  • 作者:
    Han Koo;Kyung Chan Park;Hyun Ahm Sohn;Minho Kang;Dong Joon Kim;Zee-Yong Park;Sehoon Park;Sang Hyun Min;Seong-Hwan Park;Yeon-Mi You;Yohan Han;Bo-Kyung Kim;Chul-Ho Lee;Yeon-Soo Kim;Sang J. Chung;Young Il Yeom;Dong Chul Lee
  • 通讯作者:
    Dong Chul Lee
2D materials-based 3D integration for neuromorphic hardware
基于二维材料的神经形态硬件三维集成
  • DOI:
    10.1038/s41699-024-00509-1
  • 发表时间:
    2024-11-04
  • 期刊:
  • 影响因子:
    8.800
  • 作者:
    Seung Ju Kim;Hyeon-Ji Lee;Chul-Ho Lee;Ho Won Jang
  • 通讯作者:
    Ho Won Jang
"East" and "West" as Seen in the Structure of Serbian: Langauge Contact and its Consequences
塞尔维亚语结构中的“东方”与“西方”:语言接触及其后果
  • DOI:
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Kazumasa Horigane;Chul-Ho Lee;Kunihiro Kihou;Kay Fujita;Ryoichi Kajimoto;Sungdae Ji;Jun Akimitsu;石川芳郎,,小中栄一,坂井田美代子,松本正志,近藤幸一,原田宗一,大杉豊 編;Motoki Nomachi
  • 通讯作者:
    Motoki Nomachi
Novel Signal Peptides and Episomal Plasmid System for Enhanced Protein Secretion in Engineered emBacteroides/em Species
用于增强工程化拟杆菌属物种中蛋白质分泌的新型信号肽和附加体质粒系统
  • DOI:
    10.1021/acssynbio.3c00649
  • 发表时间:
    2024-02-16
  • 期刊:
  • 影响因子:
    3.900
  • 作者:
    Tae Hyun Kim;Kowoon Ju;Seong Keun Kim;Seung-Gyun Woo;Jung-Sook Lee;Chul-Ho Lee;Eugene Rha;Jonghyeok Shin;Kil Koang Kwon;Hyewon Lee;Haseong Kim;Seung-Goo Lee;Dae-Hee Lee
  • 通讯作者:
    Dae-Hee Lee

Chul-Ho Lee的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Chul-Ho Lee', 18)}}的其他基金

Collaborative Research: CNS Core: Small: Closing the Theory-Practice Gap in Understanding and Combating Epidemic Spreading on Resource-Constrained Large-Scale Networks
合作研究:CNS核心:小型:缩小理解和抗击资源有限的大规模网络上的流行病传播的理论与实践差距
  • 批准号:
    2209922
  • 财政年份:
    2021
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: CNS Core: Small: Closing the Theory-Practice Gap in Understanding and Combating Epidemic Spreading on Resource-Constrained Large-Scale Networks
合作研究:CNS核心:小型:缩小理解和抗击资源有限的大规模网络上的流行病传播的理论与实践差距
  • 批准号:
    2007828
  • 财政年份:
    2020
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
III: Small: Collaborative Research: Cost-Efficient Sampling and Estimation from Large-Scale Networks
III:小型:协作研究:大规模网络的经济高效采样和估计
  • 批准号:
    1908375
  • 财政年份:
    2019
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: III: Small: High-Performance Scheduling for Modern Database Systems
协作研究:III:小型:现代数据库系统的高性能调度
  • 批准号:
    2322973
  • 财政年份:
    2024
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: High-Performance Scheduling for Modern Database Systems
协作研究:III:小型:现代数据库系统的高性能调度
  • 批准号:
    2322974
  • 财政年份:
    2024
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: A DREAM Proactive Conversational System
合作研究:III:小型:一个梦想的主动对话系统
  • 批准号:
    2336769
  • 财政年份:
    2024
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: A DREAM Proactive Conversational System
合作研究:III:小型:一个梦想的主动对话系统
  • 批准号:
    2336768
  • 财政年份:
    2024
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
III: Small: Multiple Device Collaborative Learning in Real Heterogeneous and Dynamic Environments
III:小:真实异构动态环境中的多设备协作学习
  • 批准号:
    2311990
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: Reconstruction of Diffusion History in Cyber and Human Networks with Applications in Epidemiology and Cybersecurity
合作研究:III:小:重建网络和人类网络中的扩散历史及其在流行病学和网络安全中的应用
  • 批准号:
    2324770
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: Efficient and Robust Multi-model Data Analytics for Edge Computing
协作研究:III:小型:边缘计算的高效、稳健的多模型数据分析
  • 批准号:
    2311596
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: Efficient and Robust Multi-model Data Analytics for Edge Computing
协作研究:III:小型:边缘计算的高效、稳健的多模型数据分析
  • 批准号:
    2311598
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: Physics Guided Graph Networks for Modeling Water Dynamics in Freshwater Ecosystems
合作研究:III:小型:用于模拟淡水生态系统中水动力学的物理引导图网络
  • 批准号:
    2316306
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
Collaborative Research: III: Small: Reconstruction of Diffusion History in Cyber and Human Networks with Applications in Epidemiology and Cybersecurity
合作研究:III:小:重建网络和人类网络中的扩散历史及其在流行病学和网络安全中的应用
  • 批准号:
    2324769
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了