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

点击翻译按钮获取中文摘要

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