References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Distributed Computation of Large-scale Graph ProblemsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2015 (English)In: SODA '15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2015, 391-410 p.Conference paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Society for Industrial and Applied Mathematics, 2015. 391-410 p.
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-165842OAI: oai:DiVA.org:kth-165842DiVA: diva2:808907
##### Conference

Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) January 4-6, 2015
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt384",{id:"formSmash:j_idt384",widgetVar:"widget_formSmash_j_idt384",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt390",{id:"formSmash:j_idt390",widgetVar:"widget_formSmash_j_idt390",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt396",{id:"formSmash:j_idt396",widgetVar:"widget_formSmash_j_idt396",multiple:true});
##### Note

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have *k* machines that jointly perform computation on an arbitrary *n*-node (typically, *n* ≫ *k*) input graph. The graph is assumed to be *randomly* partitioned among the *k* ≥ 2 machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity i.e., the number of communication rounds, of solving various fundamental graph problems.

We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of Ω(*n/k*) rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an Ω(*n/k*^{2}) lower bound for connectivity ST verification and other related problems. Our lower bounds develop and use new bounds in *random-partition* communication complexity.

To complement our lower bounds, we also give algorithms for various fundamental graph problems, e.g., PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in *Õ*(*n/k*) time (the notation *Õ* hides polylog(*n*) factors and an additive polylog(*n*) term); this shows that one can achieve almost *linear* (in *k*) speedup, whereas for shortest paths, we present algorithms that run in *Õ*(*n*/O*k*) time (for (1 + ε)-factor approximation) and in *Õ*(*n/k*) time (for *O*(log *n*)-factor approximation) respectively.

Our results are a step towards understanding the complexity of distributively solving large-scale graph problems.

QC 20150520

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2015-05-20Bibliographically approvedReferences$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1123",{id:"formSmash:lower:j_idt1123",widgetVar:"widget_formSmash_lower_j_idt1123",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1124_j_idt1126",{id:"formSmash:lower:j_idt1124:j_idt1126",widgetVar:"widget_formSmash_lower_j_idt1124_j_idt1126",target:"formSmash:lower:j_idt1124:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});