Home // IMMM 2020, The Tenth International Conference on Advances in Information Mining and Management // View article

A Randomized Sampling Algorithm based on Triangle for Community Extraction in Graphs

Authors:
Yanting Li
Ying Huo

Keywords: Triangle, Monocchromatic edge, Dense subgraph, Pattern extraction, Randomized sampling

Abstract:
The techniques of sampling play a vital role in extracting communities from graphs. Most of sampling algoritms mainly take the advantage of the degree distribution or the weight of edge. However, it may lead to huge consumption of memory usage and computation time because of the complicated structure of graphs and the noise inherent of algorithm. We propose a novel randomized sampling algorithm, which is a trianglebased sampling algorithm. A random value Rv colors each node uniformly. An edge is considered as a monochromatic edge if its two endpoints receive the same random value. The third edge of atriangle T will be sampled if two edges of the triangle T are sampled. The triangle T that formed by three monochromatic edges is the smallest sampling unit in graph G. An extracted community contains at least one triangle. Overviewing, experimental results demonstrate that the proposed algorithm extracts sufficiently dense subgraphs and significantly reduces computation time compared to the reservior sampling algorithm and graph priority sampling algorithm.

Pages: 1 to 9

Copyright: Copyright (c) IARIA, 2020

Publication date: September 27, 2020

Published in: conference

ISSN: 2326-9332

ISBN: 978-1-61208-806-8

Location: Lisbon, Portugal

Dates: from September 27, 2020 to October 1, 2020