Querying and Mining Dynamics in Evolving Graphs and Networks

在许多应用程序中，大量复杂数据被建模为图或网络。通常情况下，这些图表和网络一直在发展，例如社交网络中的互动和地理网络/通信网络中的流量。分析和挖掘不断发展的图和网络使我们能够理解过去无法全面捕获的复杂行为。动态在不断发展的图和网络中是一种美。分析和利用不断发展的图形和网络中的动态，为我们提供了前所未有的力量来征服大数据，同时也为我们带来了巨大的技术挑战。本研究计划旨在抓住机遇，及时、切实地应对技术挑战。

In many applications, huge amounts of complex data are modeled as graphs or networks. More often than not, such graphs and networks are evolving all the time, such as interactions in social networks and traffics in geographical networks/communication networks. Analyzing and mining evolving graphs and networks enable us to understand sophisticated behaviors that cannot be captured comprehensively in the past. Dynamics are a beauty in evolving graphs and networks. Analyzing and making good use of dynamics in evolving graphs and networks provide us unprecedented power to conquer big data, and, at the same time, post grand technical challenges. This proposed research program is to embrace the opportunities and address the technical challenges in a timely and practical manner. We will design practical and principled analytics tasks and develop efficient and effective methods. Specifically, we will identify a series of novel tasks that are practically useful to capture dynamics in evolving graphs and networks and, at the same time, are computationally feasible or approximate-able. Those tasks include both data statistics queries and machine learning tasks. Second, we will develop principled algorithmic approaches and data structures that are effective and efficient for those target tasks. Third, we will build a big graph and network data system as a platform to integrate our algorithmic inventions, and conduct case studies in real application scenarios to verify and evaluate our research development and produce practical impact. This proposed research program continues my long-term endeavor to conquer massive sophisticated data. The ultimate objective is to develop business intelligence based on dynamic graph and network data, and train HQP equipped with the up-to-date knowledge and skills and capable of producing innovations in industry and academia. We divide the proposed research program into three projects. First, we will study how to model dynamics in not-evolving networks with various constraints and preferences. Second, we will investigate methods analyzing and mining dynamics in evolving networks. Last, we will build a distributed big graph data system for analyzing and mining dynamics in evolving networks. We will build a distributed graph big data system as a platform to integrate our algorithmic inventions and focus on scalability using cloud computing. The proposed research program will systematically investigate a series of novel research problems and lead to fruitful publications in premier academic venues. The research outcome will advance the frontier in this fast-growing area and produce substantial impact in academia. HQP will be trained in the program to meet the deadly demand from both academia and industry in this area. We will invite our industry partners to test drive the outcome in this proposed research. Some techniques and some components of the graph database system may likely be adopted by some partners.