Abstract

Many relational classification problems involve estimating joint probability distributions over sets of nodes (and possibly edges) in relational graphs. Since exact estimation is infeasible even for moderately sized graphs, a variety of approximate methods have been proposed. One such approach is relaxation labeling, or label propagation, which works iteratively by propagating the labels (or associated probabilities) of initially labeled nodes throughout the networked data. Different label propagation techniques have been used for approximate inference making in graph–based semi–supervised learning problems. From the perspective of network dynamics, label propagation corresponds to some kind of an activation spreading in the network. Clearly, such an activation process is affected by the structural and statistical properties of the network. There has been an extensive amount of work on modeling various dynamical processes on complex networks. For instance, recent research has examined the role of scale–free degree distribution on the critical behavior of various epidemic models. Here we focus on another important property of networks, modularity, which is the tendency of nodes to partition themselves into clusters. Specifically, we are interested in how the activation process is affected by the network modularity.
We consider a random graph consisting of N= Na+ Nb nodes of two different type, a and b. The probabilities of edges between nodes of different types are γaa, γbb and γab= γba, and the average connectivity between nodes of the respective types are then zaa= γaaNa, zbb= γbbNb, zab= γabNb and zba= γabNa. We want to find …

Date

October 31, 2025

Authors

Aram Galstyan, Paul R Cohen