Analysis of the Semi-synchronous Approach to Large-scale Parallel Community Finding
|Title:||Analysis of the Semi-synchronous Approach to Large-scale Parallel Community Finding||Authors:||Duriakova, Erika
Hurley, Neil J.
|Permanent link:||http://hdl.handle.net/10197/6113||Date:||Oct-2014||Abstract:||Community-finding in graphs is the process of identifying highly cohesive vertex subsets. Recently the vertex-centric approach has been found effective for scalable graph processing and is implemented in systems such as Graph Lab and Pregel. In the vertex-centric approach, the analysis is decomposed into a set of local computations at each vertex of the graph, with results propagated to neighbours along the vertexs edges. Many community finding algorithms area menable to this approach as they are based on the optimisation of an objective through a process of iterative local update (ILU), in which vertices are successively moved to the community of one of their neighbours in order to achieve the highest local gain in the quality of the objective. The sequential processing of such iterative algorithms generally benefits from an asynchronous approach, where a vertex update uses the most recent state as generated by the previous update of vertices in its neighbourhood. When vertices are distributed over a parallel machine, the asynchronous approach can encounter race conditions that impact on its performance and destroy the consistency of the results. Alternatively,a semi-synchronous approach ensures that only non-conflicting vertices are updated simultaneously. In this paper we study the semi-synchronous approach to ILU algorithms for community finding on social networks. Because of the heavy-tailed vertex distribution, the order inwhich vertex updates are applied in asynchronous ILU can greatly impact both convergence time and quality of the found communities. We study the impact of ordering on the distributed label propagation and modularity maximisation algorithms implemented on a shared-memory multicore architecture.We demonstrate that the semi-synchronous ILU approach is competitive in time and quality with the asynchronous approach, while allowing the analyst to maintain consistent control over update ordering. Thus, our implementation results in a more robust and predictable performance and provides control over the order in which the node labels are updated, which is crucial to obtaining the correct trade-off between running time and quality of communities on many graph classes.||Funding Details:||Science Foundation Ireland||Type of material:||Conference Publication||Publisher:||ACM||Copyright (published version):||2014 ACM||Keywords:||Machine Learning & Statistics;Iterative local update;Parallel graph algorithms;Community detection algorithms;Semi-synchronous Graph Algorithms||DOI:||10.1145/2660460.2660474||Language:||en||Status of Item:||Peer reviewed||Conference Details:||ACM Conference on Online Social Network Analysis, Dublin Ireland,1-2 October, 2014|
|Appears in Collections:||Insight Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.