EECS500 Fall 2011 Department Seminar

Ruoming Jin
Mining Graphs with Uncertainty
Kent State University
White Bldg., Room 411
11:30am - 12:30pm

Networks are often inherent with uncertainty: in a communication network, a link can be unreliable and may fail with a certain probability; in a transportation system, a road can be jammed or completely broken down; in a protein interaction network, the pairwiseinteraction is derived from (approximate) statistical models; in a social network, trust and influence issues may impact the likelihood of social interactions. Uncertainty gives rise to a new dimension of difficulty in graph mining: many measurements and existing mining tools which target the deterministic networks cannot directly be applied on uncertain graphs. For example, the simple reachabilityproblem which can be easily computed in linear time in deterministic graphs, becomes a #P-complete problem in the uncertain scenario.
In this talk, I will discuss two fundamental problems in managing and mining uncertain graph.  The first one is the distance-constraint reachability(DCR) problem, which asks given two vertices s and t in an uncertain graph G, what is the probability that the distance from s to t is less than or equal to a user-defined threshold d. The DCR problem takes both reachabilityand distance into


RuomingJin is an Associate Professor in the Department of Computer Science at Kent State University. He received the PhD degree in computer science from the Ohio State University in 2005. His research interests include data mining (especially graph mining), graph databases, and cloud computing. He has published over 80 technical papers and many appear in the top data mining and database conferences and journals, including KDD, ICDM, SIGMOD, VLDB, TODS, and TKDE etc. He has served as senior PCs and PCs for numerous international data mining conferences and has co-chairs the four international workshops on mining multiple information sources. He is also a recipient of the prestigious NSF CAREER award.