Abstract
In our recent work, we developed a probabilistic framework for structural analysis of networks. In that framework, we start from sampling a network by a symmetric bivariate distribution and use that bivariate distribution to de ne various concepts, including relative centrality, centrality, community strength, and modularity. Based on these concepts, we then proposed a class of local community detection algorithms. One drawback for this framework is that the bivariate distribution has to be symmetric and that limits its applicability to undirected networks. The main objective of this paper is to extend such a framework to the setting where asymmetric bivariate distribution can be allowed. Our approach for the extension is to introduce Markov chains into the framework. We show that relative centrality, centrality, community strength and modularity can be extended in a similar manner. However, various properties, in particular the reciprocity property, are much weaker than before. As such, the local community detection algorithms need to be further modi ed by taking a larger neighboring set into account. By using the state aggregation property of Markov chains, we also develop a method for modularity preserving state reduction of a Markov chain. This method allows us to reduce the size of the states of a Markov chain while preserving its modularity. With such a state reduction method, we are then able to perform fast community detection for directed networks with a large number of nodes. In this paper, we also propose several methods of mapping directed networks to Markov chains, including random walks, PageRank and di usion. All these mappings have their own merits in structural analysis of networks. In particular, the di usion approach allows us to detect communities with respect to various time scales and we show that the community strength of a community under di usion is decreasing in time.