Professor Narsingh Deo,
(Fellow of the IEEE, Fellow of the ACM, Fellow of the AAAS, and Fellow of ICA)
Millican Chair Professor
Director, Center for Parallel Computation
School of EECS
University of Central Florida
Orlando, FL, 32816-2362
Voice: (407) 823-6336 Fax: (407)-823-5419
Abstract: Complex Networks such as the Internet, the World Wide Web (WWW), as well as various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the classical Erdös-Rényi random graphs. One such property inherent to these web-like complex networks is the existence of communities. Mining for and identifying Web-based communities, for example, has an enormous potential for application. Therefore, communities have recently been explored in several disciplines—graph theory, physics, statistics, sociology, biology, and linguistics. A community may informally be defined as a locally-dense subgraph, of a significant size, in a much larger globally-sparse graph. An optimal extraction of communities has been shown to be NP-complete. We must, therefore, devise approximate algorithms. In this talk we will present a quick overview of the community-discovery algorithms and present new heuristic for community identification. That is, a new heuristic for identifying the community structure around a given set of seed vertices, using only their neighborhood information. Since identifying communities can be an extremely compute-intensive task, parallel computation has a critical role in the solution. We will discuss both sequential and parallel heuristics.
Keynote Speaker's Short Biography: Professor Narsingh Deo is known for his work in computational graph theory, combinatorial computing, and parallel algorithms. He holds the Charles N. Millican Eminent Scholar’s Chair in Computer Science (since 1986) and is the Director of the Center for Parallel Computation at University of Central Florida, Orlando. Prior to this, he was a Professor of Computer Science at Washington State University (1977- 86), and the department chair. Before that he was a Professor of Electrical Engineering and Computer Science at the IIT, Kanpur (1971-77), and a Member of Technical Staff at Jet Propulsion Laboratory (1966-71). He received a Ph.D. from Northwestern University and an MS from CalTech. He has held Visiting Professorships at several institutions--including at the University of Illinois, Urbana; University of Nebraska, Lincoln; Indian Institute of Science, Bangalore; and IBM's T. J. Watson Research Center; ETH, Zurich; University of Sao Paulo, Brazil, Oak Ridge National Lab., Australian National University, Chuo University, Tokyo.
A Fellow of the IEEE, a Fellow of the ACM, a Fellow of the AAAS, and a Fellow of ICA (Institute of Combinatorics and its Applications), Dr. Deo has authored four textbooks on graph theory, discrete optimization, and combinatorial computing. He has published over 200 refereed research papers, and holds a number of patents in computer hardware. Among his numerous awards and honors are NASA's Apollo Achievement Award (1969) and Florida’s Governor's Award for Outstanding Contribution to High Tech Research (1989), and several research and teaching awards from University of Central Florida. He has served as an editor/guest editor/ member of the editorial board for various journals--including the IEEE Trans. on Circuits & Systems, the Journal for Parallel and Distributed Computing; theJournal of Supercomputing, and the VLSI Design Journal. He is currently the president of the Forum for Interdisciplinary Mathematics.
