|
Abstract:
|
Community detection is one of the most important tasks in network analysis. Previously, we analyzed the limits of detectability when the communities are persistent over time using BP equations in a spatio-temporal graph. However, most real networks have link persistency. Here, we study the detectability limits in a DC-SBM when both communities and links are persistent. In this setting, the added short loops can complicate convergence of BP equations. Generally, the BP equations are exact in two scenarios: strong interactions in a tree like network, and for many weak interactions as in quantum BP formulation. The latter can be helpful, when we model the temporal network as a static network, considering the history of types of each node. Using this setting, called a spatio-historical graph, we introduce a message passing algorithm to infer the communities, and apply several approximations to reduce its complexity. To investigate the limits, we use spatio-temporal setting, ignoring possible convergence issues near phase transitions. We show the improvement of detectability in regions with larger contrast between inner cluster link persistency versus outer cluster link persistency.
|
