Homophilic Graph

graph-theory

Definition

Homophilic Graph

A homophilic graph is a graph in which nodes tend to connect to other nodes that are similar in their labels or features. This structural pattern is rooted in the sociological principle of homophily.

Formally, for an undirected graph $G=(V,E)$ with node labels $y:V\to \mathcal{Y}$, the graph exhibits homophily when:

$$\mathbb{P}(y_u=y_v\mid (u,v)\in E)\gg \mathbb{P}(y_u=y_v)$$

That is, the probability that two neighbours share the same label is much higher than the prior probability of label agreement in the graph.

Edge Homophily Ratio

A common empirical measure of homophily is the edge homophily ratio:

$$h=\frac{|\{(u,v)\in E:y_u=y_v\}|}{|E|}$$

where $h\in [0,1]$. Values close to $1$ indicate strong homophily; values close to $0$ indicate strong heterophily.