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

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

基本信息

  • 批准号:
    1910749
  • 负责人:
  • 金额:
    $ 25万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2019
  • 资助国家:
    美国
  • 起止时间:
    2019-10-01 至 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)建立一个理论框架,通过在给定成本预算的困难访问环境下优化平衡样本质量和数量之间的权衡,构建一套具有成本效益的抽样政策,(ii)设计一个自适应随机游走类,通过充分利用过去的信息来实现所获得样本的最小时间相关性,并通过集体控制随机游走来实现最大空间探索,以及 (iii) 将标准 MCMC 工具包扩展到更快、更具成本效益的探索的可行的子图/配置和图上的计算/优化,以及广泛的验证,以在现实中创建实用且可用的解决方案。这项研究对广泛的多学科应用具有很高的潜在影响,包括对大规模图进行采样以进行统计推断和有效估计,以及用于各个学科中组合优化的随机算法,其中标准 MCMC 方法一直占主导地位,但也受到限制我们的理解。该奖项反映了 NSF 的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(7)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Minimizing File Transfer Time in Opportunistic Spectrum Access Model
在机会频谱访问模型中最小化文件传输时间
  • DOI:
    10.1109/tmc.2022.3212926
  • 发表时间:
    2022-10
  • 期刊:
  • 影响因子:
    7.9
  • 作者:
    Hu, Jie;Doshi, Vishwaraj;Eun, Do Young
  • 通讯作者:
    Eun, Do Young
Opportunistic Spectrum Access: Does Maximizing Throughput Minimize File Transfer Time?
机会性频谱访问:最大化吞吐量是否可以最小化文件传输时间?
Trapping Malicious Crawlers in Social Networks
在社交网络中捕获恶意爬虫
Fiedler Vector Approximation via Interacting RandomWalks
通过交互随机游走进行费德勒矢量逼近
Self-Repellent Random Walks on General Graphs - Achieving Minimal Sampling Variance via Nonlinear Markov Chains
一般图上的自排斥随机游走 - 通过非线性马尔可夫链实现最小采样方差
  • DOI:
  • 发表时间:
    2023-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Doshi, Vishwaraj;Hu, Jie;Eun, Do Young
  • 通讯作者:
    Eun, Do Young
{{ 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 }}

Do Young Eun其他文献

A Distributed Wake-Up Scheduling for Opportunistic Forwarding in Wireless Sensor Networks
无线传感器网络中机会转发的分布式唤醒调度
On the rao-blackwellization and its application for graph sampling via neighborhood exploration
关于 rao-blackwellization 及其通过邻域探索进行图采样的应用
Toward stochastic anatomy of inter-meeting time distribution under general mobility models
一般流动模型下会议间时间分布的随机剖析
Exploiting Heterogeneity for Improving Forwarding Performance in Mobile Opportunistic Networks: An Analytic Approach
利用异构性提高移动机会网络的转发性能:一种分析方法
Energy-Aware Stochastic UAV-Assisted Surveillance
能量感知随机无人机辅助监视

Do Young Eun的其他文献

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

{{ truncateString('Do Young Eun', 18)}}的其他基金

Collaborative Research: CNS Core: Small: Closing the Theory-Practice Gap in Understanding and Combating Epidemic Spreading on Resource-Constrained Large-Scale Networks
合作研究:CNS核心:小型:缩小理解和抗击资源有限的大规模网络上的流行病传播的理论与实践差距
  • 批准号:
    2007423
  • 财政年份:
    2020
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
NeTS: Small: Distributed and Efficient Randomized Algorithms for Large Networks
NeTS:小型:大型网络的分布式高效随机算法
  • 批准号:
    1217341
  • 财政年份:
    2012
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
NEDG: Efficient Design and Control of Heterogeneous Mobile Networks: Beyond Poisson Regime
NEDG:异构移动网络的高效设计和控制:超越泊松法则
  • 批准号:
    0831825
  • 财政年份:
    2008
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
TF-SING: A Theoretical Foundation of Spatio-Temporal Mobility Modeling and Induced Link-Level Dynamics
TF-SING:时空移动性建模和诱导链路级动态的理论基础
  • 批准号:
    0830680
  • 财政年份:
    2008
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
CAREER: A Stochastic Approach to the Design of Communication Networks: An Alternative to Fluid Modeling
职业生涯:通信网络设计的随机方法:流体建模的替代方法
  • 批准号:
    0545893
  • 财政年份:
    2006
  • 资助金额:
    $ 25万
  • 项目类别:
    Continuing Grant

相似国自然基金

小分子代谢物Catechin与TRPV1相互作用激活外周感觉神经元介导尿毒症瘙痒的机制研究
  • 批准号:
    82371229
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
DHEA抑制小胶质细胞Fis1乳酸化修饰减轻POCD的机制
  • 批准号:
    82301369
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
SETDB1调控小胶质细胞功能及参与阿尔茨海默病发病机制的研究
  • 批准号:
    82371419
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
PTBP1驱动H4K12la/BRD4/HIF1α复合物-PKM2正反馈环路促进非小细胞肺癌糖代谢重编程的机制研究及治疗方案探索
  • 批准号:
    82303616
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

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
Collaborative Research: III: Small: Efficient and Robust Multi-model Data Analytics for Edge Computing
协作研究:III:小型:边缘计算的高效、稳健的多模型数据分析
  • 批准号:
    2311596
  • 财政年份:
    2023
  • 资助金额:
    $ 25万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了