Algorithmic Tools for Network Analysis

Abstract

Network analysis is a crucial technique used in various fields such as computer science, telecommunications, transportation, social sciences, and biology. Its importance includes optimizing network performance, understanding social and organizational structures, and detecting fraud or misinformation. In this thesis, we propose algorithmic results on several aspects of network analysis.

The Abelian sandpile model is recognized as the first dynamical system discovered exhibiting self-organized criticality. We present algorithms that compute the final state of the sandpile instance on various classes of graphs, solving the \textit{sandpile prediction} problem on: (1) general graphs, with further analyses on regular graphs, expander graphs, and hypercubes. (2) trees and paths, surpassing previous methods in time complexity.

To analyze the structure and dynamics of networks, counting motifs is one of the most popular methods, as they are considered the basic construction block of the network. In this thesis, we introduce several tools developed for counting motifs on bipartite networks.

Despite its importance, counting (p,q)-bicliques is very challenging due to its exponential increase with respect to p and q. We present a new sampling-based method that produces a high-accuracy approximate counting of (p,q)-bicliques, with provably error guarantee and unbiasedness.

In another line of work, we consider the temporal bipartite graphs, which edges carry timestamps. To capture the dynamic nature of relationships, we consider counting butterflies ((2,2)-bicliques) in temporal bipartite graphs within specified time windows, called the historical butterfly counting problem. We present a hardness result between memory usage and query time for this problem and a new index algorithm that surpasses the hardness when applied to power-law graphs, with outstanding empirical performance.

Lastly, we discuss tools that find the polarized community in the network. A classical model that applies to networks to deal with polarization is the signed graphs, which have positive and negative edges between vertices. A signed graph is balanced if it can be decomposed into two disjoint sets such that positive edges are between vertices in the same set while negative edges are between vertices from different sets. This notion of balance is strict in that no edge can disobey the condition, which seldom appears in reality. To address this phenomenon, we propose a new model for identifying balanced subgraphs with tolerance in signed graphs and a new heuristic algorithm that computes maximal balanced subgraphs under the new tolerance model.