Spectra of Large Random Graphs And Applications In Community Detection
大型随机图谱及其在社区检测中的应用
基本信息
- 批准号:1712630
- 负责人:
- 金额:$ 15万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2017
- 资助国家:美国
- 起止时间:2017-08-01 至 2019-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Our society is currently producing and collecting tremendous amounts of data, which needs to be sifted through and categorized meaningfully in order to lead to informed decision-making. From social networks to biological ones, the problems of community detection and clustering are paramount to understanding the nature of the network; as such, efficient and reliable algorithms for these problems are of utmost importance. Devising, analyzing, and benchmarking such algorithms often rely heavily on random matrix and random graph theory, as studies have shown that large network characteristics can often be replicated (and more easily studied) via random graph models. Thus, good theoretical results on the spectra of large random graphs are needed to understand the typical behavior, as well as the limitations of community detection algorithms.The PI will work on a variety of problems, ranging from the theoretical (spectral of random graphs) to the applied (proposing and analyzing community detection algorithms). Some of the models considered will include the Stochastic Block Model and variants thereof, especially at the limit of sparseness (when average node connectivity is either large and constant or goes to infinity slower than any power of the network size). On the more theoretical side, the PI will work on problems from spectral gap (which controls properties like mixing, but also the possibility of exact community recovery in certain networks) to the empirical spectral distribution (which can be used to establish the nature of the network). The PI will also work on threshold bounds for various regimes of community detection in these graph models, and will produce software for numerically computing the asymptotical spectral distributions for a large variety of random graphs.
我们的社会目前正在产生和收集大量的数据,需要对这些数据进行有意义的筛选和分类,以便做出明智的决策。从社交网络到生物网络,社区检测和聚类问题对于理解网络的性质至关重要;因此,有效和可靠的算法对于这些问题至关重要。设计、分析和基准测试这些算法通常严重依赖于随机矩阵和随机图论,因为研究表明,大型网络特征通常可以通过随机图模型复制(并且更容易研究)。因此,我们需要对大型随机图的谱进行良好的理论研究,以了解其典型行为以及社区检测算法的局限性。PI将研究各种问题,从理论(随机图的谱)到应用(提出和分析社区检测算法)。考虑的一些模型将包括随机块模型及其变体,特别是在稀疏性的限制下(当平均节点连接性较大且恒定或比网络大小的任何幂慢到无穷大时)。在理论方面,PI将研究从频谱间隙(控制混合等属性,以及某些网络中精确社区恢复的可能性)到经验频谱分布(可用于确定网络的性质)的问题。PI还将研究这些图形模型中社区检测的各种制度的阈值界限,并将生成用于数值计算各种随机图形的渐近谱分布的软件。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
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 }}
Ioana Dumitriu其他文献
Smallest eigenvalue distributions for $\beta$-Jacobi ensembles
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
Ioana Dumitriu - 通讯作者:
Ioana Dumitriu
On expansion of $G_{n, d}$ with respect to $G_{m, d}$
关于 $G_{n, d}$ 相对于 $G_{m, d}$ 的展开
- DOI:
10.2140/apde.2023.16.571 - 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
Ioana Dumitriu;Mary Radcliffe - 通讯作者:
Mary Radcliffe
Eigenvalue statistics for beta-ensembles
- DOI:
- 发表时间:
2003 - 期刊:
- 影响因子:0
- 作者:
Ioana Dumitriu - 通讯作者:
Ioana Dumitriu
DISTRIBUTIONS OF THE EXTREME EIGENVALUES OF THE COMPLEX JACOBI RANDOM MATRIX ENSEMBLE
复雅可比随机矩阵系综的极值分布
- DOI:
- 发表时间:
2005 - 期刊:
- 影响因子:0
- 作者:
P. Koev;Ioana Dumitriu - 通讯作者:
Ioana Dumitriu
Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
异质随机块模型中的相对密度和精确恢复
- DOI:
- 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
Amin Jalali;Q. Han;Ioana Dumitriu;Maryam Fazel - 通讯作者:
Maryam Fazel
Ioana Dumitriu的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Ioana Dumitriu', 18)}}的其他基金
Far apart: outliers, extremal eigenvalues, and spectral gaps in random graphs and random matrices
相距较远:随机图和随机矩阵中的异常值、极值特征值和谱间隙
- 批准号:
2154099 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
Spectra of Large Random Graphs And Applications In Community Detection
大型随机图谱及其在社区检测中的应用
- 批准号:
1949617 - 财政年份:2019
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
Workshop on Numerical Linear Algebra and Optimization
数值线性代数与最优化研讨会
- 批准号:
1314406 - 财政年份:2013
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
CAREER: Synergistic interactions between Numerical Linear Algebra and Stochastic Eigenanalysis (Random Matrix Theory)
职业:数值线性代数和随机特征分析(随机矩阵理论)之间的协同相互作用
- 批准号:
0847661 - 财政年份:2009
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
相似国自然基金
水稻穗粒数调控关键因子LARGE6的分子遗传网络解析
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
量子自旋液体中拓扑拟粒子的性质:量子蒙特卡罗和新的large-N理论
- 批准号:
- 批准年份:2020
- 资助金额:62 万元
- 项目类别:面上项目
甘蓝型油菜Large Grain基因调控粒重的分子机制研究
- 批准号:31972875
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
Large PB/PB小鼠 视网膜新生血管模型的研究
- 批准号:30971650
- 批准年份:2009
- 资助金额:8.0 万元
- 项目类别:面上项目
基因discs large在果蝇卵母细胞的后端定位及其体轴极性形成中的作用机制
- 批准号:30800648
- 批准年份:2008
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
LARGE基因对口腔癌细胞中α-DG糖基化及表达的分子调控
- 批准号:30772435
- 批准年份:2007
- 资助金额:29.0 万元
- 项目类别:面上项目
相似海外基金
Large Graph Limits of Stochastic Processes on Random Graphs
随机图上随机过程的大图极限
- 批准号:
EP/Y027795/1 - 财政年份:2024
- 资助金额:
$ 15万 - 项目类别:
Research Grant
Collaborative Research: Adaptive Gaussian Markov Random Fields for Large-scale Discrete Optimization via Simulation
协作研究:通过仿真实现大规模离散优化的自适应高斯马尔可夫随机场
- 批准号:
2243210 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
Large-scale universal behaviour of Random Interfaces and Stochastic Operators
随机接口和随机算子的大规模通用行为
- 批准号:
MR/W008246/1 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Fellowship
Stochastic Models with Random Times: Long-Time Behavior and Large Population Limit
具有随机时间的随机模型:长时间行为和大群体限制
- 批准号:
2206038 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
Diffusion in random media: Quantifying the large-scale effects
随机介质中的扩散:量化大规模效应
- 批准号:
EP/W018616/1 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Fellowship
Random structures from large networks and systems
大型网络和系统的随机结构
- 批准号:
RGPIN-2019-04173 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Discovery Grants Program - Individual
Large Deviations and Extremes for Random Matrices, Tensors, and Fields
随机矩阵、张量和场的大偏差和极值
- 批准号:
2154029 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
Standard Grant
Large deviations in random planar geometry
随机平面几何形状的大偏差
- 批准号:
572476-2022 - 财政年份:2022
- 资助金额:
$ 15万 - 项目类别:
University Undergraduate Student Research Awards
Random structures from large networks and systems
大型网络和系统的随机结构
- 批准号:
RGPIN-2019-04173 - 财政年份:2021
- 资助金额:
$ 15万 - 项目类别:
Discovery Grants Program - Individual