2018/12/24 by Michel de Rougemont, de Rougemont, Michel, Guillaume Vimont +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Peer-to-Peer Network Technologies #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1812.09867
openalex publication_date 2018/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study how to detect clusters in a graph defined by a stream of edges, without storing the entire graph. We extend the approach to dynamic graphs defined by the most recent edges of the stream and to several streams. The \em content correlation of two streams ρ(t) is the Jaccard similarity of their clusters in the windows before time t. We propose a simple and efficient method to approximate this correlation online and show that for dynamic random graphs which follow a power law degree distribution, we can guarantee a good approximation. As an application, we follow Twitter streams and compute their content correlations online. We then propose a \em search by correlation where answers to sets of keywords are entirely based on the small correlations of the streams. Answers are ordered by the correlations, and explanations can be traced with the stored clusters.