NDLI: Fast Parallel Algorithms for Edge-Switching to Achieve a Target Visit Rate in Heterogeneous Graphs

Content Provider	IEEE Xplore Digital Library
Author	Bhuiyan, H. Jiangzhuo Chen Khan, M. Marathe, M.V.
Copyright Year	2014
Description	Author affiliation: Dept. of Comput. Sci., Virginia Tech, Blacksburg, VA, USA (Bhuiyan, H.; Marathe, M.V.) \|\| Virginia Bioinf. Inst., Virginia Tech, Blacksburg, VA, USA (Jiangzhuo Chen; Khan, M.)
Abstract	An edge switch is an operation on a network (graph) where two edges are selected randomly and one of their end vertices are swapped with each other. Usually, a sequence of these operations are performed to generate network perturbations having the same degree sequence of the original network. Edge switch operations have important applications in graph theory and network analysis, such as in generating random networks with a given degree sequence, modeling and analyzing dynamic networks (e.g., peer-to-peer networks), studying various dynamic phenomena over a network (e.g., disease dynamics over a social contact network). The growth of real-world networks motivates the need to develop efficient parallel algorithms for performing a large sequence of edge switch operations. The dependencies among successive edge switch operations and the requirement of keeping the graph simple (i.e., no self-loops or parallel edges) as the edges are switched lead to significant challenges in designing a parallel algorithm. Addressing these challenges requires complex synchronization and communication among the processors. In this paper, we present a distributed memory parallel algorithm for switching edges in massive networks (networks with billions of edges) and achieve a speedup factor of 85 with 1024 processors. One of the steps in our edge switch algorithm requires the computation of multinomial random variables in parallel. The paper presents the first non-trivial parallel algorithm for the problem. The algorithm achieves a speedup of 925 using 1024 processors.
Starting Page	60
Ending Page	69
File Size	541412
Page Count	10
File Format	PDF
ISBN	9781479956180
ISSN	01903918
DOI	10.1109/ICPP.2014.15
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-09-09
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Switches Program processors Parallel algorithms Image edge detection Random variables Partitioning algorithms Synchronization parallel algorithms edge switch massive networks multinomial distribution
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fast Parallel Algorithms for Edge-Switching to Achieve a Target Visit Rate in Heterogeneous Graphs

Parallel algorithms for switching edges in heterogeneous graphs

Fast parallel community detection algorithm based on modularity

Parallel Modularity-Based Community Detection on Large-Scale Graphs

Output-Sensitive Parallel Algorithm for Polygon Clipping

Parallel Algorithms for Edge Detection in an Image

Efficient Parallel Community Detection in Large Edge-Intensive Networks

A fast parallel algorithm for counting triangles in graphs using dynamic load balancing

A Space-Efficient Parallel Algorithm for Counting Exact Triangles in Massive Networks

Fast Parallel Algorithms for Edge-Switching to Achieve a Target Visit Rate in Heterogeneous Graphs

Similar Documents

Fast Parallel Algorithms for Edge-Switching to Achieve a Target Visit Rate in Heterogeneous Graphs

Parallel algorithms for switching edges in heterogeneous graphs

Fast parallel community detection algorithm based on modularity

Parallel Modularity-Based Community Detection on Large-Scale Graphs

Output-Sensitive Parallel Algorithm for Polygon Clipping

Parallel Algorithms for Edge Detection in an Image

Efficient Parallel Community Detection in Large Edge-Intensive Networks

A fast parallel algorithm for counting triangles in graphs using dynamic load balancing

A Space-Efficient Parallel Algorithm for Counting Exact Triangles in Massive Networks

Fast Parallel Algorithms for Edge-Switching to Achieve a Target Visit Rate in Heterogeneous Graphs