[Research] CONFIRMED : lab meeting on *Monday*

[Purnamrita Sarkar]

Hi All,

Here are the title and abstract:

A Scalable External Memory Graph Partitioning Algorithm to Reduce Diskseeks
in Random Walks

This paper introduces an algorithm to generate efficient disk-resident
representations of graphs that are too large to 
fit in main memory. The
representation is efficient in the sense that stepping through paths of
connected nodes in the graph (e.g. simulating a random walk) involves
relatively few disk seeks. Since a broad class of graph-based similarity
metrics (e.g. personalized pagerank, hitting and commute times, simrank)
can be estimated by simulating random walks in a graph, this algorithm
will strongly benefi
t applications such as link prediction in social
networks, personalized graph search, fraud detection and collaborative

ltering. We build on previous work that has shown that personalized
pagerank based graph-partitioning has desirable properties, and our
primary contribution is an efficient algorithm based purely on sequential
sweeps through 
les to generate such partitions. In addition to the
disk-based algorithm, this paper provides error bounds for computing
approximate personalized pagerank vectors, which can be used to 
find good
local partitions (graph cuts with small conductance) near a given starting
point in a graph. We also present some new theoretical properties of
personalized pagerank which enables us to scale our algorithm up-to real
world graphs with up-to 69 million edges. We empirically demonstrate the
utility of the disk-based partitioning for link prediction tasks on real
world disk-resident graphs like DBLP, Citeseer and Live- Journal. In
addition to vanilla random walk simulations, we present deterministic
algorithms for quickly computing top k neighbors of a node in personalized
pagerank using our disk-resident graph representation.

Purna


On Sun, November 15, 2009 9:54 am, Artur Dubrawski wrote:
> Purna's talk is going to happen!
>
>
> Where: NSH 1507
> When: MONDAY 11/16 at noon
> Food: yes
>
>
> See you all there
> Artur
>
>
>
> Artur Dubrawski wrote:
>
>> Hello,
>>
>>
>> The meeting tomorrow is CANCELED b/c Purna is down with cold
>> (get well soon Purna!).
>>
>>
>> We have tentatively rescheduled it for Monday, Nov 16th, lunchtime.
>> Details will be provided when available.
>>
>>
>> Artur
>>
>>
>> Artur Dubrawski wrote:
>>
>>> Dear Autonians,
>>>
>>>
>>> This week we will hear Purna Sarkar talk about her current
>>> work into useful and manageable analysis or large networks. The title
>>> and abstract will be provided soon by the presenter herself.
>>>
>>> Place: Gates 6501
>>> Time: noon, Nov 11th
>>> Food: yes
>>>
>>>
>>> See you all there
>>> Artur
>>>
>>>
>>>
>>> _______________________________________________
>>> Research mailing list
>>> Research at autonlab.org
>>> https://www.autonlab.org/mailman/listinfo/research
>>>
>>>
>>>
>>
>>
>
> _______________________________________________
> Research mailing list
> Research at autonlab.org
> https://www.autonlab.org/mailman/listinfo/research
>
>
>