Scale-Invariant Strength Assortativity of Streaming Butterflies

Abstract

Bipartite graphs are rich data structures with prevalent applications and identifier structural features. However, less is known about their growth patterns, particularly in streaming settings. Current works study the patterns of static or aggregated temporal graphs optimized for certain down-stream analytics or ignoring multipartite/non-stationary data distributions, emergence patterns of subgraphs, and streaming paradigms. To address these, we perform statistical network analysis over web log streams and identify the governing patterns underlying the bursty emergence of mesoscopic building blocks, 2,2-bicliques known as butterflies, leading to a phenomenon that we call "scale-invariant strength assortativity of streaming butterflies". We provide the graph-theoretic explanation of this phenomenon. We further introduce a set of micro-mechanics in the body of a streaming growth algorithm, sGrow, to pinpoint the generative origins. sGrow supports streaming paradigms, emergence of 4-vertex graphlets, and provides user-specified configurations for the scale, burstiness, level of strength assortativity, probability of out-of-order records, generation time, and time-sensitive connections. Comprehensive Evaluations on pattern reproducing and stress testing validate the effectiveness, efficiency, and robustness of sGrow in realization of the observed patterns independent of initial conditions, scale, temporal characteristics, and model configurations. Theoretical and experimental analysis verify the robust ability of sGrow in generating streaming graphs based on user-specified configurations that affect the scale and burstiness of the stream, level of strength assortativity, probability of-of-order streaming records, generation time, and time-sensitive connections.

arXiv commentSubmitted for publication

References in corpus (33)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Assortative mixing in networks
• The architecture of complex weighted networks
• Random graphs with arbitrary degree distributions and their applications
• Dynamical and correlation properties of the Internet
• Why social networks are different from other types of networks
• Detecting rich-club ordering in complex networks
• Modularity and community detection in bipartite networks
• Complex network approaches to nonlinear time series analysis
• The Rich-Club Phenomenon In The Internet Topology
• Weighted evolving networks: coupling topology and weights dynamics
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Weighted Evolving Networks
• Module identification in bipartite and directed networks
• Degree Distributions of Growing Networks
• Modeling the evolution of weighted networks
• Temporal motifs in time-dependent networks
• Bipartite Graphs as Models of Complex Networks
• Scaling properties of scale-free evolving networks: Continuous approach
• Core-periphery organization of complex networks
• Log-Networks
• Weighted Assortative And Disassortative Networks Model
• Robustness and Assortativity for Diffusion-like Processes in Scale-free Networks
• Random Graph Modeling: A survey of the concepts
• Knowing a network by walking on it: emergence of scaling
• Transitivity and degree assortativity explained: The bipartite structure of social networks
• Degree distributions of bipartite networks and their projections
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Likelihood-based approach to discriminate mixtures of network models that vary in time
• sGrapp: Butterfly Approximation in Streaming Graphs
• Butterfly-Core Community Search over Labeled Graphs