Discovering Important Patterns across and within Networks via Network Alignment and Clustering

Networks can be used to model real-world phenomena in a variety of domains. Many computational strategies have been defined to take advantage of the power of networks and answer different applied questions. This dissertation aims to advance two of the most popular computational strategies for network analysis: network alignment (NA) and network clustering (NC).

First, the focus is on NA, which aims to find a node mapping (i.e., alignment) between compared networks that identifies network regions of topological or functional similarity. NA is a computationally hard problem due to the underlying subgraph isomorphism problem. Thus, heuristics known as NA methods are needed. In this context, this dissertation introduces a novel framework for fair evaluation of NA methods, a novel idea of maximizing both node and edge conservation during the alignment process as opposed just one of them, and the first NA method that combines two complementary NA types and is thus able to outperform methods of any individual NA type.

Second, the focus is on NC, which aims to divide a network into groups (i.e., clusters) of “topologically related” (e.g., densely interconnected or topologically similar) nodes. Even for static data, the problem of network clustering is complex. For dynamic data, the problem is even more complex, due to an additional dimension of the data - their temporal (evolving) nature. Since the problem is computationally intractable, heuristic approaches need to be sought. In this dissertation, we present a novel approach to performing NC on dynamic data that not only captures temporal information early in the clustering process, but is also the first dynamic network clustering method to generate partitions based on the notion of topological similarity.

While NA and NC are defined as two different computational strategies, they are actually related to each other, as they both aim to group similar nodes together. Given their relatedness, this dissertation concludes by combining NA and NC into a single strategy with the goal of simultaneously finding similar regions both within and across networks, unlike existing methods that do each of these two tasks individually.