[Nrg-l] NRG this Monday

Niky Riga inki at cs.bu.edu
Fri May 13 13:17:53 EDT 2005


It is my pleasure to announce that this Monday John will be giving a talk
at our weekly NRG meeting. We are going to meet as usual at 4:00pm at
the graduate lounge. The abstrack of the talk follows.


Title: Unveiling Hidden Topologies: Applications, Algorithms and

Abstract: We consider a set of applications in Internet topology 
measurement, bioinformatics and physics in which the aim is to identify
statistical or structural properties of a network whose nodes are either
fully or partially known in advance, but whose edge connectivity is not
known. In exact versions of the problems, the goal is to minimize the
number of application-specific probes needed to correctly
identify a subtopology (e.g. a hidden matching in one gene sequencing
In approximate versions of the problems, the goal is to maximize the
accuracy of estimates produced on a fixed measurement budget
(e.g. parameters describing the degree distribution of an Internet
topology). In addition to discussing algorithms and lower bounds, we
consider the role played by measurement artifacts
such as sampling bias, and the impact that modeling assumptions have on
algorithmic performance.

[This is a reprise of an invited talk given at the "Models of Real-World
Random Networks" workshop at MSRI in Berkeley:

question = ( to ) ? be : ! be;
                -- Wm. Shakespeare

More information about the Nrg-l mailing list