BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//6.6.3//EN
TZID:America/Chicago
X-WR-TIMEZONE:America/Chicago
BEGIN:VEVENT
UID:0-996@ece.iastate.edu
DTSTART;TZID=America/Chicago:20190307T110000
DTEND;TZID=America/Chicago:20190307T120000
DTSTAMP:20190304T183401Z
URL:https://www.ece.iastate.edu/seminars-and-events/graduate-seminar-apurb
a-das/
SUMMARY:Graduate Seminar with Apurba Das: Incremental and Parallel Algorith
ms for Dense Subgraph Detection - 3043 ECpE Building Addition - Mar 07\, 2
019 11:00
DESCRIPTION:Speaker: Apurba Das\, ECpE Graduate Student\n\nAdvisor: Srika
nta Tirthapura\n\nTitle: Incremental and Parallel Algorithms for Dense Su
bgraph Detection\n\nAbstract: The task of maintaining densely connected s
ubgraphs from a continuously evolving graph is important because it solves
many practical problems that require constant monitoring over the continu
ous stream of linked data often represented as a graph. For example\, cont
inuous maintenance of a certain group of closely connected nodes can revea
l unusual activity over the transaction network\, identification\, and evo
lution of active groups in social network etc. On the other hand\, mining
these structures from graph data is often expensive because of the complex
ity of the computation and the volume of the structures (the number of den
sely connected structures can be of exponential order on the number of ver
tices in the graph). One way to deal with the expensive computations is to
consider parallel computation.\n\nWe advance the state of the art by deve
loping provably efficient algorithms for mining maximal cliques and maxima
l bicliques.\n\nFirst we consider the design of efficient algorithms for t
he maintenance of maximal cliques and maximal bicliques in an evolving net
work. We observe that it is important to locate the region of the graph in
the event of the update so that we can maintain the structures by computi
ng the changes exactly where it is located. Following this observation\, w
e design efficient techniques that find appropriate subgraphs for identify
ing the changes in the structures. We prove that our algorithms can mainta
in dense structures efficiently. More specifically\, we show that our algo
rithms can quickly compute the changes when it is small irrespective of th
e size of the graph. We empirically evaluate our algorithms and show that
our algorithms significantly outperform the state of the art algorithms.\n
\nNext\, we consider parallel computation for efficient utilization of the
multiple cores in a multi-core computing system so that the expensive min
ing tasks can be eased off and we can achieve better speedup than their ef
ficient sequential counterparts. We design shared memory parallel algorith
ms for the mining of maximal cliques and we prove the efficiency of the pa
rallel algorithms through showing that the total work performed by the par
allel algorithm is equivalent to the time complexity of the best sequentia
l algorithm for doing the same task. Our experimental study shows that we
achieve good speedup over the prior state of the art parallel algorithms a
nd significant speedup over the state of the art sequential algorithms. We
also show that our parallel algorithms scale almost linearly with the inc
rease in the processor cores.
CATEGORIES:Events,Seminars,Seminars and Events
LOCATION:3043 ECpE Building Addition\, Coover Hall\, Ames\, Iowa\, 50011\,
United States
GEO:42.0285;-93.6511
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=Coover Hall\, Ames\, Iowa\,
50011\, United States;X-APPLE-RADIUS=100;X-TITLE=3043 ECpE Building Addit
ion:geo:42.0285,-93.6511
END:VEVENT
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:STANDARD
DTSTART:20181104T010000
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
END:STANDARD
END:VTIMEZONE
END:VCALENDAR