Computer Science Seminar Series
A Structural Clustering Algorithm for Networks and Its Applications
March 19, 3:00pm
Weir Hall, Room 235
Xiaowei Xu
Professor and Director of Advanced Knowledge Discovery and Data Mining
Research Laboratory
Department of Information Science
University of Arkansas at Little Rock
Abstract:
Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. Many algorithms find clusters by maximizing the number of intra-cluster edges. While such algorithms find useful and interesting structures, they tend to fail to identify and isolate two kinds of vertices that play special roles - vertices that bridge clusters (hubs) and vertices that are marginally connected to clusters (outliers). Identifying hubs is useful for applications such as viral marketing and epidemiology since hubs are responsible for spreading ideas or disease. In contrast, outliers have little or no influence, and may be isolated as noise in the data. Recently, we proposed a novel algorithm called SCAN (Structural Clustering Algorithm for Networks), which detects clusters, hubs and outliers in networks. It clusters vertices based on a structural similarity measure. The algorithm is fast and efficient, visiting each vertex only once. An empirical evaluation of the method using both synthetic and real datasets demonstrates superior performance over other methods such as the modularity-based algorithms.
Biography:Dr. Xu is a leading researcher in the area of data mining. He published over 40 papers in premier journals and conferences including IEEE Transactions on Knowledge and Data Engineering (TKDE), ACM SIGKDD International Conferences in Knowledge Discovery and Data Mining (KDD), International Conferences in Very Large Databases (VLDB), etc. His scientific work has been included in popular data mining textbooks. Dr. Xu is one of the most cited authors in computer science according to CiteSeer. His research is supported by federal funding agencies including National Institute of Health (NIH), Federal Food and Drug Administration (FDA), German Federal Ministry of Education and Research (BMFT). In addition, he served as consultant for many industrial companies including Simens AG and Acxiom Corporation. In his career he served as program committee members and session chairs for many leading forums of data mining including KDD, IEEE International Conferences on Data Mining (ICDM), SIAM International Conference on Data Mining (SDM), etc. Furthermore, he served as reviewer for international prestigious journals such as TKDE.