Large-scale structure in complex networks

复杂网络中的大规模结构

• 批准号: 1107796
• 负责人: Mark Newman
• 金额: $ 32万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-15 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1107796&HistoricalAwards=false
• 关键词: Large; scale; structure; complex; networks

The investigator and his colleagues study the large-scale structure of real-world networks, such as social, biological, and information networks. Several specific projects will be undertaken. The first will focus on the classic problem of community detection in networks and the development of compact objective functions for assessing community quality and effective strategies for their optimization. The methods proposed improve on previous ones in being rigorously motivated, utilizing as much as possible of the information stored in a network, and avoiding some of the pitfalls of previous approaches, such as resolution limits. A second project will develop methods for general structural inference in networks based on a combination of expectation--maximization (EM) algorithms with Monte Carlo and belief propagation methods. A particular strength of these approaches is that, because they optimize marginal probabilities, they have the potential to avoid overfitting and offer strategies for solving model selection problems. Several further projects focus on the extension of these techniques to more complex forms of network structure, including overlapping vertex classes, hierarchical structure, and dependence on general classes of hidden variables.Many systems of scientific interest can be represented as networks, from the Internet to biological networks to social networks. In the last decade copious amounts of network data have become available in different fields, but in many cases these data are dense and bewildering, presenting a substantial challenge to the user trying to make sense of their structure. The fundamental question addressed in this research is how we can gain new understanding about physical, biological, and social systems from their network structure. For instance, the investigator and his collaborators will develop methods for detecting groups of closely interacting nodes in networks, such as cliques of individuals in social networks, or groups of related web sites on the web. They will also tackle general questions of using network structure to deduce unknown properties of network nodes. If, for instance, there are several different types of nodes in a network, such as classes of chemicals in a metabolic network in the cell, how can we identify the types from network structure alone, without measuring them directly (which may be difficult or costly)? The funded research will create a range of mathematical tools that can be applied to problems in this area. The methods to be developed have a number of possible applications, including new techniques to aid researchers working on biological and social networks, commercial applications in online social networks, and software applications in data visualization and automatic data summarization, among others.

研究人员和他的同事研究现实世界网络的大规模结构，如社会，生物和信息网络。 将开展若干具体项目。 第一个将集中在网络中的社区检测的经典问题和紧凑的目标函数评估社区质量和有效的优化策略的发展。 所提出的方法改进了以前的方法，具有严格的动机，尽可能多地利用存储在网络中的信息，并避免了以前方法的一些陷阱，例如分辨率限制。 第二个项目将基于期望最大化（EM）算法与蒙特卡罗和置信传播方法的结合，开发网络中通用结构推理的方法。 这些方法的一个特殊优势在于，由于它们优化了边际概率，因此它们有可能避免过拟合，并提供解决模型选择问题的策略。 一些进一步的项目集中在这些技术的扩展到更复杂的网络结构形式，包括重叠顶点类，层次结构，并依赖于一般类的隐变量。许多科学感兴趣的系统可以表示为网络，从互联网到生物网络社交网络。 在过去的十年中，大量的网络数据已经在不同的领域中可用，但在许多情况下，这些数据是密集和令人困惑的，给试图理解其结构的用户带来了巨大的挑战。 本研究的基本问题是如何从网络结构中获得对物理、生物和社会系统的新认识。 例如，研究人员和他的合作者将开发用于检测网络中密切交互的节点组的方法，例如社交网络中的个人团体或网络上的相关网站组。 他们还将解决使用网络结构来推断网络节点的未知属性的一般问题。 例如，如果网络中有几种不同类型的节点，例如细胞代谢网络中的化学物质类别，我们如何仅从网络结构中识别类型，而不直接测量它们（这可能很困难或昂贵）？ 资助的研究将创建一系列数学工具，可应用于这一领域的问题。 待开发的方法有许多可能的应用，包括帮助研究人员研究生物和社交网络的新技术，在线社交网络中的商业应用，以及数据可视化和自动数据汇总中的软件应用等。