Ryan A. Rossi
ABSTRACT
Given a large time-evolving graph, how can we model and characterize the temporal behaviors of individual nodes (and network states)? How can we model the behavioral transition patterns of nodes? We propose a temporal behavior model that captures the "roles" of nodes in the graph and how they evolve over time. The proposed dynamic behavioral mixed-membership model (DBMM) is scalable, fully automatic (no user-defined parameters), non-parametric/data-driven (no specific functional form or parameterization), interpretable (identifies explainable patterns), and flexible (applicable to dynamic and streaming networks). Moreover, the interpretable behavioral roles are generalizable and computationally efficient. We applied our model for (a) identifying patterns and trends of nodes and network states based on the temporal behavior, (b) predicting future structural changes, and (c) detecting unusual temporal behavior transitions. The experiments demonstrate the scalability, flexibility, and effectiveness of our model for identifying interesting patterns, detecting unusual structural transitions, and predicting the future structural changes of the network and individual nodes.
- J. Abello, T. Eliassi-Rad, and N. Devanur. Detecting novel discrepancies in communication networks. In ICDM, 2010. Google Scholar
Digital Library
- S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In SIGKDD, 2007. Google ScholarDigital Library
- L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD, 2006. Google ScholarDigital Library
- M. Cha, A. Mislove, and K. P. Gummadi. A Measurement-driven Analysis of Information Propagation in the Flickr Social Network. In WWW, 2009. Google ScholarDigital Library
- D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In KDD, 2006. Google ScholarDigital Library
- A. Dhamdhere and C. Dovrolis. Ten years in the evolution of the internet ecosystem. In SIGCOMM, 2008. Google ScholarDigital Library
- A. Dhamdhere and C. Dovrolis. The internet is at: modeling the transition from a transit hierarchy to a peering mesh. In In CoNEXT, page 21, 2010. Google ScholarDigital Library
- D. Dunlavy, T. Kolda, and E. Acar. Temporal link prediction using matrix and tensor factorizations. TKDD, 5(2):10, 2011. Google ScholarDigital Library
- W. Fu, L. Song, and E. Xing. Dynamic mixed membership blockmodel for evolving networks. In ICML, pages 329--336. ACM, 2009. Google ScholarDigital Library
- M. Gotz, J. Leskovec, M. McGlohon, and C. Faloutsos. Modeling blog dynamics. In ICWSM, 2009.Google ScholarCross Ref
- D. Greene, D. Doyle, and P. Cunningham. Tracking the evolution of communities in dynamic social networks. In ASONAM, 2010. Google ScholarDigital Library
- H. Habiba, Y. Yu, T. Berger-Wolf, and J. Saia. Finding spread blockers in dynamic networks. In ASONAM, 2008. Google ScholarDigital Library
- D. Hand and R. Till. A simple generalisation of the area under the roc curve for multiple class classification problems. Machine Learning, 45(2):171--186, 2001. Google ScholarDigital Library
- K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, and C. Faloutsos. It's Who You Know: Graph Mining Using Recursive Structural Features. In SIGKDD, pages 1--10, 2011. Google ScholarDigital Library
- K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, and C. Faloutsos. RolX: Role Extraction and Mining in Large Networks. In KDD, 2012.Google ScholarDigital Library
- J. Leskovec, L. Adamic, and B. Huberman. The dynamics of viral marketing. TWEB, 1(1):1--39, 2007. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, 2005. Google ScholarDigital Library
- Y. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. Tseng. Analyzing communities and their evolutions in dynamic social networks. TKDD, 3(2):8, 2009. Google ScholarDigital Library
- P. Mahadevan, D. Krioukov, M. Fomenkov, X. Dimitropoulos, et al. The Internet AS-level topology: three data sources and one definitive metric. ACM SIGCOMM CCR, 36(1):17--26, 2006. Google ScholarDigital Library
- J. O'Madadhain, J. Hutchins, and P. Smyth. Prediction and ranking algorithms for event-based network data. SIGKDD Explorations, 7(2):30, 2005. Google ScholarDigital Library
- R. Pan and J. Saramaki. Path lengths, correlations, and centrality in temporal networks. arXiv:1101.5913, 2011.Google Scholar
- S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming pattern discovery in multiple time-series. In VLDB, 2005. Google ScholarDigital Library
- R. Rossi, B. Gallagher, J. Neville, and K. Henderson. Modeling temporal behavior in large networks: A dynamic mixed-membership model. In LLNL-TR-514271, 2011.Google ScholarCross Ref
- R. Rossi and D. Gleich. Dynamic pagerank using evolving teleportation. In WAW, pages 126--137. LNCS 7323, 2012. Google ScholarDigital Library
- R. Rossi, L. McDowell, D. Aha, and J. Neville. Transforming graph data for statistical relational learning. Journal of Artificial Intelligence (JAIR), 2012. Google ScholarDigital Library
- R. Rossi and J. Neville. Time-evolving relational classification and ensemble methods. In PAKDD, 2012. Google ScholarDigital Library
- J. Sun, C. Faloutsos, S. Papadimitriou, and P. Yu. Graphscope: parameter-free mining of large time-evolving graphs. In KDD, 2007. Google ScholarDigital Library
- L. Tang, H. Liu, J. Zhang, and Z. Nazeri. Community evolution in dynamic multi-mode networks. In SIGKDD, pages 677--685. ACM, 2008. Google ScholarDigital Library
- X. Wang, X. Liu, and D. Loguinov. Modeling the Evolution of Degree Correlation in Scale-Free Topology Generators. In INFOCOM, 2007.Google Scholar
- E. Xing, W. Fu, and L. Song. A state-space mixed membership blockmodel for dynamic network tomography. Ann. Appl. Stat., 4(2):535--566, 2010.Google ScholarCross Ref
- J. Yang and J. Leskovec. Patterns of temporal variation in online media. In WSDM, 2011. Google ScholarDigital Library
Index Terms
- Modeling dynamic behavior in large evolving graphs
Recommendations
Modelling User Behavior Dynamics with Embeddings
CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge ManagementUnderstanding user interaction behaviors remains a challenging problem. Quantifying behavior dynamics over time as users complete tasks has only been done in specific domains. In this paper, we present a user behavior model built using behavior ...
Modeling Dynamic Social Behaviors with Time-Evolving Graphs for User Behavior Predictions
Database Systems for Advanced ApplicationsAbstractThe full coverage of Wi-Fi signals and the popularization of intelligent card systems provide a large volume of data that contain human mobility patterns. Effectively utilizing such data to make user behavior predictions finds useful applications ...
Detection of anomalous modeling behavior: a goal-driven data mining approach
MODELS '22: Proceedings of the 25th International Conference on Model Driven Engineering Languages and Systems: Companion ProceedingsPrecise and timely detection of anomalous modeling behaviors is critical for both teaching and application of modeling methods. Existing methods usually focus on evaluating the modeling results rather than mining the knowledge hidden in the modeling ...
Comments