sGrapp: Butterfly Approximation in Streaming Graphs
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.
Sheshbolouki, Aida, and M. Tamer Özsu. "sGrapp: Butterfly Approximation in Streaming Graphs." arXiv preprint arXiv:2101.12334 (2021).
Read the paper (Will update the most recent version soon)
Delightful Event: sGrapp is accepted to appear in ACM Transactions on Knowledge Discovery from Data!
EIC comment: "The paper discusses butterfly formation in graphs. A very well written paper that is a pleasure to read. Some minor changes are suggested"
Emergence of Global Synchronization in Directed Excitatory Networks of Type I Neurons
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.
Ziaeemehr, Abolfazl, Mina Zarei, and Aida Sheshbolouki. "Emergence of global synchronization in directed excitatory networks of type I neurons." Scientific reports 10, no. 1 (2020): 1-11.
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.
Sheshbolouki, Aida, Mina Zarei, and Hamid Sarbazi-Azad. "The role of leadership in the synchronization of directed complex networks." Journal of Statistical Mechanics: Theory and Experiment 2015, no. 10 (2015): P10022.
Are Feedback Loops Destructive to Synchronization?
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.