  Homophily is the principle whereby "similarity breeds connections". We give a
quantitative formulation of this principle within networks. Given a network and
a labeled partition of its vertices, the vector indexed by each class of the
partition, whose entries are the number of edges of the subgraphs induced by
the corresponding classes, is viewed as the observed outcome of the random
vector described by picking labeled partitions at random among labeled
partitions whose classes have the same cardinalities as the given one. In this
perspective, the value of any homophily score $\Theta$, namely a non decreasing
real valued function in the sizes of subgraphs induced by the classes of the
partition, evaluated at the observed outcome, can be thought of as the observed
value of a random variable. Consequently, according to the score $\Theta$, the
input network is homophillic at the significance level $\alpha$ whenever the
one-sided tail probability of observing a value of $\Theta$ at least as extreme
as the observed one, is smaller than $\alpha$. Since, as we show, even
approximating $\alpha$ is an NP-hard problem, we resort to classical tails
inequality to bound $\alpha$ from above. These upper bounds, obtained by
specializing $\Theta$, yield a class of quantifiers of network homophily.
Computing the upper bounds requires the knowledge of the covariance matrix of
the random vector which was not previously known within the random coloring
model. In this paper we close this gap, giving a meaningful, easy to compute
class of indices for measuring network homophily. As demonstrated in real-world
network applications, these indices are effective, reliable, and lead to new
discoveries that could not be captured by the current state of the art.
