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

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

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.