English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We design a space efficient algorithm that approximates the transitivity(global clustering coefficient) and total triangle count with only a singlepass through a graph given as a stream of edges. Our procedure is based on theclassic probabilistic result, the birthday paradox. When the transitivity isconstant and there are more edges than wedges (common properties for socialnetworks), we can prove that our algorithm requires $O(\sqrt{n})$ space ($n$ isthe number of vertices) to provide accurate estimates. We run a detailed set ofexperiments on a variety of real graphs and demonstrate that the memoryrequirement of the algorithm is a tiny fraction of the graph. For example, evenfor a graph with 200 million edges, our algorithm stores just 60,000 edges togive accurate results. Being a single pass streaming algorithm, our procedurealso maintains a real-time estimate of the transitivity/number of triangles ofa graph, by storing a minuscule fraction of edges.

A space efficient streaming algorithm for triangle counting using the birthday paradox