Higher Order Structure Distorts Local Information in Networks

Local information available to individual nodes in a network may significantly differ from the global information. Such local information bias can significantly affect collective phenomena in networks, including the outcomes of contagious processes and opinion dynamics. To quantify local information bias, we investigate the strong friendship paradox in networks, which occurs when a majority of a node's neighbors have more neighbors than it does itself. Our analysis identified certain properties that determine the strength of the paradox in a network: attribute-degree correlation, network degree-degree correlation and neighbor-neighbor degree correlation, which are degree correlations one step beyond those of neighboring nodes. We develop models that can accurately infer the strength of the paradoxes in synthetic and real-world networks from the network structural features. In addition, we also discovered that the neighbor-neighbor degree correlation is significant in real world networks. Understanding how the paradox biases local observations can inform better measurements of network structure and our understanding of collective phenomena.