Network Community Structures in Markov Influence Graphs

Identifying a network's community structure is essential for understanding its internal organizations, dynamics, and functionalities. However, this field of study remains challenging due to various reasons, such as misrepresentation of node influence, heterogeneous travel times, NP-hardness, and unstable outputs. This study introduces two novel algorithms-- Self-loop KDA and Weighted KDA--that deal with these problems by representing the network in special forms of Markov chain or Markov Influence Graph (MIG). Our contribution is fourfold. First, we prove that it is possible to find a MIG form that preserves the original node influence of any network. Second, this representation is utilized in the Self-loop KDA to uncover a network's community structure. Third, we introduce the Weighted KDA, which incorporates heterogeneous travel times into the network's community structure, providing a more realistic representation of many empirical networks. Through numerical and empirical analysis, we demonstrate that varying transition times can influence community structure, particularly in the merging of disconnected communities. Finally, both algorithms are stable, deterministic, and run in polynomial time.