A Method for Discovering Dynamic Network Motifs by Encoding Topic Propagation

Marketing campaigns using social media services aim to exploit social connections to propagate messages to potential customers. However, social activities often give rise to multiple network structures and some may be more effective in achieving the communication objectives than others. This led us to investigate a problem: given an observed sequence of messages and a social network that includes individuals involved in messaging, does the network structure ´explain´ the observed propagation. To facilitate this investigation, we designed a method for encoding propagation events relative to the structure of a given network. The resulting transmission codes capture both the temporal and the structural characteristics of the propagation. We analyze the codes for maximal repeats and k-common sub strings to uncover dynamic network motifs within the propagation trace. By considering the dynamic motifs and the connected graph components, we can determine how the propagation events relate to the specific network. As a case study, we applied our method to rumor topics in Twitter and analyzed their propagation trails relative to the ´follower´ network. The study demonstrates the computational feasibility of our approach and illustrates the use of dynamic motifs to reason about the impact of follower relationship rumor propagation in Twitter.