How large is your graph?

DOI10.4230/LIPICS.DISC.2017.34MaRDI QIDQ6487507zbMATH OpenFDO

Authors Varun Kanade, Frederik Mallmann-Trenn, Víctor Verdugo

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.34

zbMATH Keywords

estimationrandom walkssocial networks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Social networks; opinion dynamics (91D30)

Recommendations

• Brief announcement: How large is your graph?
• Sublinear Algorithms for Local Graph-Centrality Estimation
• Approximately counting triangles in sublinear time
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Estimating graph parameters with random walks

Cited in

(6)

• How unproportional must a graph be?
• Interactive proofs for social graphs
• Estimating sizes of social networks via biased sampling
• Brief announcement: How large is your graph?
• Sublinear Algorithms for Local Graph-Centrality Estimation
• On the estimate of the size of a directed graph

This page was built for publication: How large is your graph?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487507)