ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Counting Triangles in Large Graphs by Random Sampling (2016)

Institute of Electrical and Electronics Engineers (IEEE)

In: IEEE Transactions on Knowledge and Data Engineering

add to mindlist on the mindlist

Details

Publication Date: 2016-07-08

Description: The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates.

Print ISSN: 1041-4347

Electronic ISSN: 1558-2191

Topics: Computer Science

Published by Institute of Electrical and Electronics Engineers (IEEE) on behalf of The IEEE Computer Society.

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit