RI: Small: Algorithms for Sampling Similar Graphs Using Subgraph Signatures

RI：小：使用子图签名对相似图进行采样的算法

• 批准号: 0916686
• 负责人: Vishwanathan Swaminathan
• 金额: $ 49.45万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916686&HistoricalAwards=false
• 关键词: RI; Small; Algorithms; Sampling; Similar

Abstract below:Graphs and networks are a natural representation across a wide rangeof disciplines and domains. Statistical tools have recently beenbrought to bear on the analysis of graphs, yielding rich dividends invarious application areas. The aim of this project is to use toolsfrom statistics and graph theory to develop algorithms that generatesimilar graphs efficiently. Since graph data is often expensive tocollect, it is desirable to synthetically generate graphs. To bewidely applicable however, the generated graphs need to both preservethe semantics of the original data (i.e., be drawn from the samedistribution) and be efficient to compute.Two key questions form the core emphasis of the current project.First, how does one measure similarity between two graphs? Second, howcan this notion of similarity be used to generate new graphs? On thetopic of similarity, the project will investigate representations topreserve global properties, propose new, efficient, representationsfor signatures, and explore sampling techniques and their convergencebehavior. On the topic of generation of new graphs, the project willdevelop an exponential random graph model using signatures,investigate feature selection via regularization, propose novelmethods to sample from the exponential random graph model and noveltechniques to produce proposal graphs, and provide rigorous empiricalvalidation across a range of application areas.The project will facilitate the study of large complex structures ofthe kind frequently encountered in domains like theoretical ecology,social networks, and chemo-informatics, allowing researchers in thesedomains to leverage statistical network analysis tools to identifysignificant patterns and understand algorithm performance.For further information see the project web page:URL: http://www.stat.purdue.edu/~vishy/graphs.html

摘要如下：图和网络是一个自然的代表性，跨越了广泛的学科和领域。统计工具最近被用于分析图表，在各个应用领域产生了丰富的红利。这个项目的目的是使用统计学和图论的工具来开发有效生成相似图的算法。由于图形数据通常是昂贵的收集，它是可取的综合生成图。然而，为了广泛应用，生成的图需要既保留原始数据的语义（即，从相同的分布中抽取），并且计算效率高。两个关键问题构成了当前项目的核心重点。首先，如何测量两个图之间的相似性？第二，相似性的概念如何被用来生成新的图？关于相似性的主题，该项目将研究保留全局属性的表示，提出新的，有效的签名表示，并探索采样技术及其收敛行为。关于生成新图的主题，该项目将使用签名开发指数随机图模型，通过正则化研究特征选择，提出从指数随机图模型中采样的新方法和生成建议图的新技术，并在一系列应用领域提供严格的经验验证。该项目将促进对在以下领域经常遇到的大型复杂结构的研究：理论生态学、社交网络和化学信息学，使这些领域的研究人员能够利用统计网络分析工具来识别重要模式和理解算法性能。http://www.stat.purdue.edu/~vishy/graphs.html