ITR: Emerging Communities in Large Linked Networks: Theory Meets Practice

ITR：大型互联网络中的新兴社区：理论与实践的结合

• 批准号: 0312910
• 负责人: John Hopcroft
• 金额: $ 30万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0312910&HistoricalAwards=false
• 关键词: ITR; Emerging; Communities; Large; Linked

This project will develop the theory, concepts and tools to track changes and detect emerging structure in large networks. It combines a theoretical investigation of how networks and communities evolve over time with empirical studies using the NEC CiteSeer database. Clustering plays a crucial role in detecting community structure. However, tracking changes in structure over time places new demands on clustering algorithms. In particular it requires a stability not usually demanded of clustering techniques. This project starts from the premise that there actually are real communities of various sizes in the data and that these communities are invariant under changes such as random removal of 5-10% of the papers in the database.If a clustering technique gives a radically different clustering when an additional 10,000 papers are added to the database, it will be impossible to separate small changes in the evolving structure from artifacts of the clustering technique. The project builds upon a concept of natural communities of various sizes that can be identified under quite strong changes in the data. A central component of the work is to develop a principled generative model of growing random graphs which has complex evolving community structure and in which the concept of a natural community arises. Tools will be developed to find these natural communities with sufficient stability to track real changes in the clusters over time and identify when new communities emerge.The ability to track emerging trends and detect hidden structure in large networked digital data sources should be of potentially great societal benefit. In particular, it would allow the end-user to search for information in a more informed manner, and enable a pro-active approach towards emerging trends and new developments.

该项目将开发理论，概念和工具来跟踪变化并检测大型网络中的新兴结构。它结合了网络和社区如何随着时间的推移与使用NEC CiteSeer数据库的实证研究演变的理论研究。聚类在检测社区结构中起着至关重要的作用。然而，跟踪结构随时间的变化对聚类算法提出了新的要求。特别是它需要一个稳定性通常不要求聚类技术。这个项目的前提是数据中实际上存在各种大小的真实的社区，并且这些社区在数据库中随机删除5-10%的论文时是不变的。如果聚类技术在向数据库中添加额外的10，000篇论文时给出完全不同的聚类，将不可能从聚类技术的伪像中分离出演变结构中的小变化。该项目建立在各种规模的自然群落的概念基础上，这些自然群落可以在数据的强烈变化下识别。这项工作的一个核心组成部分是开发一个原则性的生成模型，不断增长的随机图，具有复杂的不断发展的社区结构，并在其中出现了一个自然社区的概念。将开发各种工具来寻找这些具有足够稳定性的自然群落，以跟踪这些群落随时间的真实的变化，并确定新群落何时出现，跟踪新兴趋势和发现大型网络数字数据源中隐藏结构的能力应具有潜在的巨大社会效益。 特别是，它将使最终用户能够以更知情的方式搜索信息，并能够对新出现的趋势和新的发展采取积极主动的办法。