Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Conference Proceeding

Conference

2014 IEEE International Congress on Big Data

Publication Version

Accepted Manuscript

Link to Published Version

https://doi.org/10.1109/BigData.Congress.2014.105

Publication Date

2014

Journal or Book Title

Proceedings of the 2014 IEEE International Congress on Big Data

First Page

707

Last Page

716

DOI

10.1109/BigData.Congress.2014.105

Conference Title

BIG DATA CONGRESS '14

Conference Date

June 27-July 2, 2014

City

Anchorage, AK

Abstract

We consider the enumeration of maximal bipartite cliques (bicliques) from a large graph, a task central to many practical data mining problems in social network analysis and bioinformatics. We present novel parallel algorithms for the MapReduce platform, and an experimental evaluation using Hadoop MapReduce. Our algorithm is based on clustering the input graph into smaller sized subgraphs, followed by processing different subgraphs in parallel. Our algorithm uses two ideas that enable it to scale to large graphs: (1) the redundancy in work between different subgraph explorations is minimized through a careful pruning of the search space, and (2) the load on different reducers is balanced through the use of an appropriate total order among the vertices. Our evaluation shows that the algorithm scales to large graphs with millions of edges and tens of millions of maximal bicliques. To our knowledge, this is the first work on maximal biclique enumeration for graphs of this scale.

Comments

This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Mukherjee, Arko Provo, and Srikanta Tirthapura. "Enumerating Maximal Bicliques from a Large Graph Using MapReduce." In Proceedings of the 2014 IEEE International Congress on Big Data, pp. 707-716. IEEE Computer Society, 2014. DOI: 10.1109/BigData.Congress.2014.105. Posted with permission.

Copyright Owner

ACM

Language

en

File Format

application/pdf

Published Version

Share

Article Location

 
COinS