Social Network Prediction Problems: Using Meta-Paths and Dynamic Heterogeneous Graph Representation for Label Propagation

Graph representations for real-world social networks in the past have missed two important elements: (i) the multiplexity of connections and (ii) representing time. This paper presents a dynamic heterogeneous graph representation for social networks that includes time in every component of the graph, that is, nodes and edges, each of different types that captures heterogeneity. We illustrate the power of this representation by presenting four time-dependent queries and a multiclass classification problem that cannot easily be handled in conventional homogeneous graph representations. As a proof of concept, we present a detailed representation of a relatively new social media platform (Steemit), which we use to illustrate both the dynamic querying capability, as well as a prediction task using label propagation algorithm (LPA). We also present temporal social media meta-paths to generalize the LPA to dynamic heterogeneous graph structures, that is, Meta-paths + LPA. To validate and compare our proposed method, we conduct an experiment using three benchmark data sets and show that our proposed method outperforms almost all four state-of-the-art algorithms in category prediction task by at least 13.79% accuracy.

History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0274) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0274). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.