CAREER: Novel Data Mining Technologies for Complex Network Analysis

A model complex network is a large system of elements (vertices) that are joined by non-trivial relationships (edges). Examples of such complex networks include the WWW, metabolic and protein networks, social networks, and economic and financial markets. The underlying principles and laws of these network systems can help us construct more effective communication mechanisms, find cures for fatal diseases, and deal with economic crises.

Building upon an innovative blend of graph theoretical, information theoretical, and statistical learning concepts and techniques, the proposed mining methodologies in this project will 1) extract network backbones which both simplify and highlight network structures, 2) measure the network difference for comparative network analysis, and 3) apply causal inference to integrate time series with network topology. In a close collaboration with domain experts from bioinformatics, political science, and software engineering, the proposed techniques have the potential to help reveal the organizational principles of biocellular systems in a dynamic environment; identify therapeutic or drug targets; illuminate how large scale software systems form and evolve; and understand how human society is organized at the individual level (social networks) and organizational level (political science). Using the popular online social networks, such as MySpace and Facebook, as "hooks", this project will attract, recruit, and prepare students from underrepresented groups including women and minorities to computer science and involve underrepresented students in the cutting-edge research.

People

• Ruoming Jin (PI)

• Ning Ruan (Ph.D. 2012, Google)

• Lin Liu (Ph.D. candidate)

• Yelong Shen (Ph.D. student)

• Nicholas Tietz (Undergraduate Student)

• Tim Fox (Undergraduate Student)

• Henry Butler (Undergraduate student)

Publications

• Lin Liu, Ruoming Jin, Charu C. Aggarwal, Yelong Shen: Reliable Clustering on Uncertain Graphs. ICDM 2012: 459-468

• Yelong Shen, Ruoming Jin, Dejing Dou, Nafisa Afrin Chowdhury, Junfeng Sun, Brigitte Piniewski, David Kil: Socialized Gaussian Process Model for Human Behavior Prediction in a Health Social Network. ICDM 2012: 1110-1115

• Yelong Shen, Ruoming Jin: Learning personal + social latent factor model for social recommendation. KDD 2012: 1303-1311

• Ruoming Jin, Ning Ruan, Saikat Dey, Jeffrey Xu Yu: SCARAB: scaling reachability computation on large graphs. SIGMOD Conference 2012: 169-180

• Ruoming Jin, Ning Ruan, Yang Xiang, Victor E. Lee: A highway-centric labeling approach for answering distance queries on large sparse graphs. SIGMOD Conference 2012: 445-456

• Ruoming Jin, Victor E. Lee, Hui Hong: Axiomatic Ranking of Network Role Similarity, in KDD'11.

• Ruoming Jin, Lin Liu, Charu C. Aggarwal, Discovering Highly Reliable Subgraphs in Uncertain Graphs, in KDD'11.

• Ning Ruan, Ruoming Jin, and Yan Huang, Distance Preserving Graph Simplification, in ICDM'11.

• Haishan Liu, Paea LePendu, Ruoming Jin, and Dejing Dou, A Hypergraph-based Method for Discovering Semantically Associated Itemsets, in ICDM'11.

• Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang, Distance-Constraint Realiability Computation in Uncertain Graphs, in VLDB'11.

• Jun Gao, Jeffrey Xu Yu, Ruoming Jin, Jiashui Zhou, Tengjiao Wang, and Dongqiang Yang, Neighborhood-Privacy Protected Shortest Distance Computing in Cloud, in SIGMOD'11.

Acknowledgements