Keynote Lecture
Detecting Overlapping Communities: A Game-Theoretic Approach
Professor Narsingh Deo
Co-author: Elham Havvaei
University of Central Florida
Orlando, FL, USA
E-mail: deo@cs.ucf.edu
Abstract: Unlike the traditional Erdos-Renyi random graphs, complex networks tend to form communities, which may informally be described as subsets of nodes densely connected among themselves but sparsely connected to nodes not in the subset. Determining the community structure of a given complex network, G, consists of identifying all such communities in G. It is an important computational problem, as it provides an insight into the functionality of the network. But extracting high-quality community structure in a large complex network is a challenging problem. Although community structures have been studied in mathematical sociology for a long time, dramatic growth of real-life complex networks--including the Internet, the World Wide Web, and various social networks—has led to various studies of the communities in complex networks in the last 15-20 years. Investigating the community structure in a dynamic network, where the network is subject to addition of new nodes and edges as well as deletion of existing nodes and edges, is even more challenging. In this paper we discuss a game-theoretic technique for detecting community structures in dynamic as well as static complex networks. In this method, each node represents a player that attempts to gain a higher payoff by joining one or more communities or by switching from one community to another. The goal of the game is to reveal community structure formed by these players (nodes) by finding a Nash-equilibrium point among them. We have developed a computationally-feasible algorithm for extracting high-quality community structure by deploying the game-theoretic techniques. The experimental results illustrating the effectiveness of the proposed method on both synthetic and real-world networks, are presented.
Brief Biography of the Speaker: Prof. Narsingh Deo is known for his work in computational graph theory, complex networks and parallel algorithms. He has held the Charles N. Millican Eminent Scholar’s Chair in Computer Science at University of Central Florida, since 1986. Prior to this, he was a Professor of Computer Science at Washington State University, where he also served as the department chair. Before that he was a Professor of Electrical Engineering and Computer Science at the Indian Institute of Technology, Kanpur, and a Member of Technical Staff at Jet Propulsion Laboratory. He has a Ph.D. (EE) from Northwestern University, an MS from Caltech, and an undergraduate degree from Indian Institute of Science, also in EE.
He has held Visiting professorships at numerous 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, Canberra; Chuo University, Tokyo; Monash University, Melbourne, Australia; and IIT/Kharagpur.
A Fellow of the IEEE, a Fellow of the ACM, and Fellow of the ICA, and a Fellow of the AAAS, Dr. Deo has authored four books and over 250 refereed research papers. He holds a number of patents in computer hardware and is a recipient of NASA's Apollo Achievement Award (1969). Among his other awards are: Gold Medal of Patna University (1956); Drake Scholar at Caltech (1959) Florida Governor's Award for Outstanding Contribution to High Tech (1989); UCF's Distinguished Researcher Award-89; UCF's Professorial Excellence Program Award (1997); UCF's Teaching Incentive Program Award (1999); and UCF’s Excellence in Graduate Teaching Award (2001). He has served as an editor/guest editor/ member of the editorial board for several journals.