Under consideration for publication in Network Science 1 Relative Centrality and Local Community Detection

In this paper, we make an attempt to develop a formal framework for what a good community should look like and how strong a community is (community strength). Through this framework we can not only provide more physical insights and unified interpretations for various structural analyses of networks such as centralities and communities, but also develop efficient algorithms for local community detection with guaranteed community strength. One of the key innovations of our framework is to incorporate the concept of relative centrality into structural analysis of networks. In our framework, relative centrality is a (probability) measure that measures how important a set of nodes in a network is with respect to another set of nodes, and it is a generalization of centrality that only measures (or ranks) how important a set of nodes in a network is with respect to the whole set of nodes in the network. Building on top of relative centrality, the community strength for a set of nodes is measured by the difference between its relative centrality with respect to itself and its centrality. A community is then a set of nodes with a nonnegative community strength. With such a definition of community, we are able to prove several mathematically equivalent statements of a community that can be intuitively explained by their socia