Assefaw Gebremedhin, Research, Network Analysis

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.


Go back to Research Areas or go side-ways to
  • Parallel Graph Algorithms
  • Coloring and Automatic Differentiation
  • Parallel Computation Models