Network Science. Networks have become a worthy modeling language for diverse phenomena in nature and society. A broad interdisciplinary field -- under the name network science -- has emerged as a result. Network science seeks to understand the structure and behavior of complex networks and to reason about dynamic processes that take place on them. I am primarily interested in the synergetic use of graph-theoretic and matrix algorithms in network analysis.
Maximum Clique Algorithms and Applications. Finding tightly connected subnetworks is a fundamental problem in network analysis. A special case is the problem of finding the largest clique -- a subnetwork in which every node is connected with every other node. The maximum clique problem is a classical NP-hard (also to approximate) in graph theory. In recent work, colleagues and I have developed a fast, branch-and-bound type maximum clique finding algorithm that has proven effective on large sparse, networks. In a follow-up work we further improved the clique finder's performance and utility and applied it to analyze various social and information networks, to compute strongly connected components in temporal networks, and to compress large graphs.
Graph Query Performance Prediction. Query performance prediction has shown benefits to query optimization and resource allocation for relational databases. Emerging applications are leading to search scenarios where workloads with heterogeneous, structure-less analytical queries are processed over large-scale graph and network data. This calls for effective models to predict the performance of graph analytical queries, which are often more involved than their relational counterparts. In a recent effort, we have begun to study and evaluate techniques for graph query performance prediction.
Papers