-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathworkshop2008.html
More file actions
206 lines (195 loc) · 11.3 KB
/
workshop2008.html
File metadata and controls
206 lines (195 loc) · 11.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"><!-- InstanceBegin template="/Templates/base.dwt" codeOutsideHTMLIsLocked="false" -->
<head>
<meta name="author" content="David A. Bader" />
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta name="description" content="GraphAnalysis.org: High performance computing for solving large-scale graph problems" />
<meta name="keywords" content="Graph Analysis, GraphAnalysis, HPC Graphs, parallel graph problems" />
<link rel="stylesheet" type="text/css" href="style.css" />
<!-- InstanceBeginEditable name="doctitle" -->
<title>GraphAnalysis.org: SIAM PP08 Workshop for HPC on Large Graphs</title>
<!-- InstanceEndEditable -->
<!-- InstanceBeginEditable name="head" -->
<style type="text/css">
<!--
.style3 {color: #0000FF}
.style5 {color: #FF0000; font-family: Verdana, Arial, Helvetica, sans-serif; font-weight: bold; font-size: large; }
.style6 {font-size: medium}
.style7 {color: #FF0000; font-family: Verdana, Arial, Helvetica, sans-serif; font-weight: bold; font-size: medium; }
-->
</style>
<!-- InstanceEndEditable -->
</head>
<body>
<div id="container">
<div id="top">
<h1><center>HPC Graph Analysis</center></h1>
</div>
<div id="leftnav">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="news.html">News</a></li>
<li><a href="benchmark/index.html">Benchmark</a></li>
<li><a href="benchmark/results.html">Results</a></li>
<li><a href="workshop2022.html">Workshop 2022</a></li>
<li><a href="workshop2021.html">Workshop 2021</a></li>
<li><a href="workshop2020.html">Workshop 2020</a></li>
<li><a href="workshop2019.html">Workshop 2019</a></li>
<li><a href="workshop2018.html">Workshop 2018</a></li>
<li><a href="workshop-CSE17.html">Workshop @CSE17</a></li>
<li><a href="workshop2017.html">Workshop 2017</a></li>
<li><a href="workshop2016.html">Workshop 2016</a></li>
<li><a href="workshop2015.html">Workshop 2015</a></li>
<li><a href="workshop2014.html">Workshop 2014</a></li>
<li><a href="workshop2013.html">Workshop 2013</a></li>
<li><a href="workshop2012-SC12.html">Workshop @SC12</a></li>
<li><a href="workshop2012.html">Workshop 2012</a></li>
<li><a href="workshop2010.html">Workshop 2010</a></li>
<li><a href="workshop2009.html">Workshop 2009</a></li>
<li><a href="workshop2008.html">Workshop 2008</a></li>
<li><a href="publications.html">Publications</a></li>
<li><a href="people.html">People</a></li>
<li><a href="links.html">Links</a></li>
<li><a href="contact.html">Contact</a></li>
</ul>
</div>
<!-- InstanceBeginEditable name="EditRegion3" -->
<div id="content">
<h3>SIAM PP08 Workshop for HPC on Large Graphs</h3>
<h4 align="center">
The Rennaissance Atlanta Hotel Downtown<br />
Atlanta, GA<br />
<br />
12-14 March 2008<br />
</h4>
<h3>Scope and Goals:</h3>
<p>Graphs are a fundamental representation of information that spans the widest possible range of computing
applications. They are particularly important to computational biology, web search, and knowledge
discovery. As the sizes of the graphs increase, the need to apply High Performance Computing (HPC) to
solve these problems is growing dramatically. This workshop represents a unique opportunity for the
community of researchers in this field and focus on the technical issues associated with applying HPC to
large graph problems. The workshop will feature several invited speakers drawn from the leaders in this
new and rapidly growing field.</p>
<h3>Location:</h3>
<p><a href="http://www.siam.org/meetings/pp08/"><img src="PP08_logo.gif" alt="PP08 logo" width="88" height="94" hspace="10" vspace="0" border="0" align="left" longdesc="http://www.siam.org/meetings/pp08/" /></a>This workshop is co-located with <a href="http://www.siam.org/meetings/pp08/">SIAM PP08</a>, held 12-14 March 2008, at the Rennaissance Atlanta Hotel Downtown in Atlanta, GA. Registration information for PP08 can be found at <a href="http://www.siam.org/meetings/pp08/reginfo.php">here</a>.</p>
<br />
<h3 align="left"><br />
Program: </h3>
<span class="style5"><br />
<span class="style6">Thursday, March 13</span></span>
<dl>
<dt><strong>1:30-1:55 Analytic Theory of Power Law Graphs</strong> </dt>
<dd><span class="style3"><em>Jeremy Kepner</em>, Massachusetts Institute of Technology</span></dd>
<dd>An analytical theory of power law graphs is presented based on the
Kronecker graph generation technique. The analysis uses Kronecker
exponentials of complete bipartite graphs to formulate the
sub-structure of such graphs. This allows various high level quantities
(e.g. degree distribution, betweenness centrality, diameter,
eigenvalues, and isoparametric ratio) to be computed directly from the
model parameters. The implications of this work on ``clustering'' and
``dendragram'' heuristics are also discussed. </dd>
<dt><strong>2:00-2:25 Parallel Algorithms for Small-world Network Analysis and Partitioning</strong> </dt>
<dd><span class="style3"><em>David A. Bader</em>, Georgia Institute of Technology </span></dd>
<dd> We present SNAP, a parallel library for exploratory analysis and
partitioning of small-world networks. SNAP includes fast, parallel
implementations of fundamental graph-theoretic kernels and topological
analysis metrics (e.g., breadth-first search, connected components,
betweenness centrality), as well as novel community structure detection
algorithms. In the talk, we highlight algorithmic details and
optimizations to achieve scalable parallel performance on small-world
graph instances.</dd>
<dt><strong>2:30-2:55 The MultiThreaded Graph Library</strong> </dt>
<dd><span class="style3"><em>Jonathan Berry</em>, Sandia National Laboratories</span><br />
The MultiThreaded Graph Library (MTGL) is a set of open-source codes for
graph algorithms that target emerging massively multithreaded
architectures. This library is based upon a kernel of the Boost Graph
Library, though it does not require Boost.
MTGL codes run on serial workstations, and can run on the Cray MTA/XMT
supercomputers. Much of the detail inherent in the programming model of
the latter machines is abstracted away from the application programmer.</dd>
<dt><strong>3:00-3:25 Tensor Decompositions for Analyzing Multi-Link Graphs</strong> </dt>
<dd><span class="style3"><em>Danny Dunlavy</em>, Tammy Kolda, and Philip Kegelmeyer, Sandia National Laboratories</span><br />
Link analysis of data represented by a graph typically focuses on a
single type of connection. However, often we want to analyze data that
has multiple linkages between objects. The goal of this talk is to show
that tensors and their decompositions provide a set of tools for
multi-link analysis. We provide examples of how tensors can be used to
understand the structure of document spaces and define similarities
based on multiple linkages.</dd>
</dl>
<span class="style7">Friday, March 14</span><br />
<dl>
<dt><strong>10:00-10:25 Parallel Primitives for Computation with Large Graphs</strong> </dt>
<dd><span class="style3"><em> Aydin Buluc</em> and John R. Gilbert, University of California, Santa Barbara </span><br />
Large combinatorial graphs appear in many applications of
high-performance computing, including computational biology,
informatics, analytics, web search, dynamical systems, and sparse matrix
methods. High-performance combinatorial computing is much less well
understood than high-performance numerical computing, where there are
standard algorithmic primitives and a deep understanding of effective
mappings of problems to computer architectures. Here we describe the
usage and implementation of sparse generalized matrix-matrix
multiplication as a primitive operation for high-performance computing
on large graphs.</dd>
<dt><strong>10:30-10:55 Kronecker Graphs</strong> </dt>
<dd><span class="style3"><em>Jure Leskovec</em>, Carnegie Mellon University </span><br />
Given a large, real graph, how can we generate a synthetic graph that is
similar, i.e., it has similar degree distribution, diameter, spectrum,
etc.? I will introduce "Kronecker graphs" model, which naturally
generates graphs with above properties, and present a fast and scalable
algorithm for fitting Kronecker model to real networks. Experiments on
large real networks show that Kronecker mimics well the patterns found
in target graphs. Once fitted, the model can be used for anonymization,
extrapolations, and graph summarization.</dd>
<dt><strong>11:00-11:25 High Performance Combinatorial Techniques for Processing Dynamic Interaction Networks</strong> </dt>
<dd><span class="style3"><em>Kamesh Madduri</em>, Georgia Institute of Technology </span><br />
Graph abstractions are extensively used to model temporal data streams
from socio-economic interactions, the world-wide web, and communication
networks. For tractable analysis of massive temporal data sets, we
require holistic schemes that couple HPC techniques, dynamic graph
algorithms, and social network analysis kernels. In this talk, we
present a computational framework for the topological analysis of
dynamic networks: we experiment with several graph representations,
identify key analysis kernels to be optimized, and discuss parallel
algorithms for large-scale graph analysis.</dd>
<dt><strong>11:30-11:55 Array Based Betweenness Centrality</strong> </dt>
<dd><span class="style3"><em>Eric Robinson</em>, Northeastern University </span><br />
The betweenness centrality metric measures the importance of a node in a
graph by examining the number of shortest paths through it.
A natural translation of a sequential BC algorithm using linear
algebraic
notation is shown. A batching parameter shifts this algorithm between<em>O(E)</em> and <em>O(V^2)</em> space, possibly providing constant speedup for small
batch values. When implemented in pMatlab, both sequential and parallel
algorithms
are shown to have reasonable performance compared to their C
counterparts.<br />
</dd>
</dl>
<h3>Workshop Co-Chairs:</h3>
<ul>
<li><a href="http://www.cc.gatech.edu/~bader">Prof. David
A. Bader</a>, Georgia Institute of Technology</li>
<li><a href="http://www.cs.ucsb.edu/~gilbert/">Prof. John R. Gilbert </a>, University of California, Santa Barbara</li>
<li><a href="http://www.mit.edu/~kepner">Dr. Jeremy Kepner</a>, MIT Lincoln Laboratory <br />
</li>
</ul>
</div>
<!-- InstanceEndEditable -->
<div id="footer">
<i>
<script language="JavaScript">
<!---//hide script from old browsers
document.write( "Last updated: "+ document.lastModified );
//end hiding contents --->
</script>
</i>
</div>
</div>
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-1564202-1";
urchinTracker();
</script>
</body>
<!-- InstanceEnd -->