sGrow: Explaining the Scale-Invariant Strength Assortativity of Streaming Butterflies

Bipartite graphs are rich data structures with prevalent applications and characteristic 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 downstream 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, 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 four-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 sGrow’s robustness in generating streaming graphs based on user-specified configurations that affect the scale and burstiness of the stream, level of strength assortativity, probability of out-of-order streaming records, generation time, and time-sensitive connections.

This paper studies the fundamental problem of butterfly (i.e. (2,2)-bicliques) counting in bipartite streaming graphs. Similar to triangles in unipartite graphs, enumerating butterflies is crucial in understanding the structure of bipartite graphs. This benefits many applications where studying the cohesion in a graph shaped data is of particular interest. Examples include investigating the structure of computational graphs or input graphs to the algorithms, as well as dynamic phenomena and analytic tasks over complex real graphs. Butterfly counting is computationally expensive, and known techniques do not scale to large graphs; the problem is even harder in streaming graphs. In this paper, following a data-driven methodology, we first conduct an empirical analysis to uncover temporal organizing principles of butterflies in real streaming graphs and then we introduce an approximate adaptive window-based algorithm, sGrapp, for counting butterflies as well as its optimized version sGrapp-x. sGrapp is designed to operate efficiently and effectively over any graph stream with any temporal behavior. Experimental studies of sGrapp and sGrapp-x show superior performance in terms of both accuracy and efficiency.

The collective behaviour of neural networks depends on the cellular and synaptic properties of the neurons. The phase-response curve (PRC) is an experimentally obtainable measure of cellular properties that quantifies the shift in the next spike time of a neuron as a function of the phase at which stimulus is delivered to that neuron. The neuronal PRCs can be classified as having either purely positive values (type I) or distinct positive and negative regions (type II). Networks of type 1 PRCs tend not to synchronize via mutual excitatory synaptic connections. We study the synchronization properties of identical type I and type II neurons, assuming unidirectional synapses. Performing the linear stability analysis and the numerical simulation of the extended Kuramoto model, we show that feedforward loop motifs favour synchronization of type I excitatory and inhibitory neurons, while feedback loop motifs destroy their synchronization tendency. Moreover, large directed networks, either without feedback motifs or with many of them, have been constructed from the same undirected backbones, and a high synchronization level is observed for directed acyclic graphs with type I neurons. It has been shown that, the synchronizability of type I neurons depends on both the directionality of the network connectivity and the topology of its undirected backbone. The abundance of feedforward motifs enhances the synchronizability of the directed acyclic graphs.

Synchronization is a phenomenon that occurs in systems of interacting units, and is widespread in nature, society and technology. Recent studies have enlightened us regarding the interplay between synchronization dynamics and interaction structure. However, most of these studies neglect that real-world networks may actually be directed and disconnected. Here, we study the synchronization of directed networks with multiple leaders using the Kuramoto model. We found that in networks with high driving strength, the steady-state frequency of each node is determined by the linear combination of leaders' natural frequencies, with structural coefficients that can be calculated using the eigenvectors of a network Laplacian matrix corresponding to zero eigenvalues. The steady-state frequencies of the nodes following multiple leaders are not fixed and have sharp peaks between consecutive time instances where leaders meet each other in the phase circle. The results suggest a new way of understanding how leadership style influences the synchronization dynamics of directed networks.

We study the effects of directionality on synchronization of dynamical networks. Performing the linear stability analysis and the numerical simulation of the Kuramoto model in directed networks, we show that balancing in- and out-degrees of all nodes enhances the synchronization of sparse networks, especially in networks with high clustering coefficient and homogeneous degree distribution. Furthermore, by omitting all the feedback loops, we show that while hierarchical directed acyclic graphs are structurally highly synchronizable, their global synchronization is too sensitive to the choice of natural frequencies and is strongly affected by noise.