Homophily of Large Weighted Networks in a Data Streaming Setting

We propose a rigorous and efficient method for evaluating homophily and heterophily in edge-weighted networks. In a network with nodes partitioned into classes, homophily (resp., heterophily) is defined as the tendency to have edges between nodes in the same class (resp., in different classes). Assuming a suitable null model, we provide a closed formula for the z-score of the total weight of homophilic/heterophilic edges for each class/pair of classes. The z-score directly measures how much this weight deviates from its expected value under the null model. In addition, we also propose a global homophily measure, that gives a significant score of how the set of all classes at a glance tend to be homophilic. The proposed statistics can be computed for very large networks since, as we show, they can be efficiently computed in a data streaming setting. For a network with n nodes and m edges, our algorithm only needs O(n) internal memory space, optimal O(m) worst case time, and a single scan of the m input edges, in any order, is required. Experimental results are shown on ten Protein-Protein Interaction networks, reporting homophily w.r.t. protein functional classes.