Spectral Algorithms for Streaming Graph Analysis: A Survey

Braznev Sarkar () and Malay Bhattacharyya ()
Additional contact information
Braznev Sarkar: Indian Institute of Engineering Science and Technology
Malay Bhattacharyya: Centre for Artificial Intelligence and Machine Learning, Indian Statistical Institute

Annals of Data Science, 2021, vol. 8, issue 4, No 1, 667-681

Abstract: Abstract Streaming data models refer to some constrained settings through which continuous flow of information regarding updates on the data becomes available. Graphs can also be represented in a streaming setting where interaction information turns out to be accessible as a stream of inclusion or exclusion of interactions. Analysis of streaming graphs helps to understand extreme-scale and dynamic real-life interactions in different forms. The growth of world wide web has drastically changed the way we look at various real-life evolving gigantic networks. This has motivated the development of streaming algorithms to be applied on graphs at scale. To achieve this scalability, sketching and sampling strategies are generally adopted to realize the different attributes of graphs. Spectrum of a graph, being one of the most appreciated characteristics, has lead to the evolution of an entire class of spectral algorithms. In this paper, we touch upon the state-of-the-art progress in streaming graph analysis with spectral algorithms. We mainly cover the latest developments in the areas like sampling, sparsification, singular value decomposition, counting problems related to local structures, analysis of global structures, partitioning, labeling, mesh processing, discovery of patterns, anomalous hotspot discovery, detection of communities, etc. on the subject of streaming graphs.

Keywords: Spectral algorithms; Steaming graph analysis; Graph processing; Graph patterns; 05C85; 35PXX; 68RXX (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s40745-020-00301-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aodasc:v:8:y:2021:i:4:d:10.1007_s40745-020-00301-0

Ordering information: This journal article can be ordered from
https://www.springer ... gement/journal/40745

DOI: 10.1007/s40745-020-00301-0

Access Statistics for this article

Annals of Data Science is currently edited by Yong Shi

More articles in Annals of Data Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().