CAREER: Graph Identification

当今世界要求我们参与、理解或以其他方式导航许多类型的网络，包括社会网络、通信网络、金融交易网络、基因调控网络、疾病传播网络、生态食品网络、传感器网络等等。这类网络上的观测数据很丰富，但提取相关数据具有挑战性。此外，这些数据通常有错误、不完整和零散，或者没有提供我们想要了解和使用的网络的简明和宏观视图。这一研究项目将开发各种方法来推断和表示最能解释观察到的实体以及这些实体之间的相互作用的基本的基础网络结构。特别是，该提案引入了称为图标识的过程抽象。其由用于识别等价的观察实体、从观察到的交互识别实体之间的链接(即，关系)、以及同时基于其互连结构将许多实体分类成类的更基本的过程组成。这个项目的一个计算挑战是集成这些基本过程，每个过程都已经由PI和其他人研究过，以高效和可扩展的方式获得整体图形识别问题的准确解决方案。这项研究对基础科学、国家安全和更好地理解当今网络社会中的隐私问题具有更广泛的影响。

Today's world requires that we participate in, comprehend, or otherwise navigate many kinds of networks, including social networks, communication networks, financial transaction networks, gene regulatory networks, disease transmission networks, ecological food networks, sensor networks and more. Observational data on such networks is plentiful, but extracting the relevant data is challenging. Furthermore, this data often has errors, is incomplete and fragmented, or otherwise does not offer a concise and big-picture view of the network that we want to understand and use. This research project will develop methods for inferring and representing the essential, underlying network structure that best accounts for observed entities and interactions between these entities. In particular, the proposal introduces a process abstraction called ?graph identification,? which is composed of more basic processes for identifying observed entities that are equivalent, identifying links (i.e., relationships) between entities from observed interactions, and simultaneously classifying many entities into classes based on their interconnection structure. A computational challenge of this project is integrating these basic processes, each of which has been studied by the PI and others, to achieve accurate solutions to the overall graph identification problem, in a manner that is efficient and scalable. This research has broader impacts for basic science, national security and a better understanding of privacy issues in today's networked society.