From micro to macro: Propagated constraints in social networks

Accurately evaluating the importance of nodes in social networks is essential to many tasks such as influential node identification, social campaign monitoring, and rumor prevention. The structural hole theory addresses this issue by quantifying the constraints among the nodes. However, the theory considers the effect of local network structure rather than the whole network structure. This introduces potential biases in the quantification of node importance. To fill this gap, we propose the concept of propagated constraints based on the structural hole theory. We assume that a node not only receives constraints from other nodes but also imposes constraints on them reciprocally. In addition, constraints can propagate along the shortest paths and reach a distant node, which results in a global measure of node importance. We also propose a constraint propagation algorithm to calculate the global constraints of nodes. Finally, we apply the algorithm to a real social network to evaluate the performance of the proposed metrics, which are compared with the state-of-the-art structural importance measures. The experimental results validate the effectiveness of the proposed measures.