[Networkit] Open Problem: Distance Profile via Sampling

Christian Staudt christian.staudt at kit.edu
Wed Sep 2 11:39:31 CEST 2015


@Matteo: Thank you for your suggestions, they were very helpful. “Neighborhood function” is the right keyword.

On 15 Aug 2015, at 17:07, Matteo Riondato <matteo at cs.brown.edu> wrote:


> For example, the HyperANF approach by Boldi, Rosa, and Vigna (WWW’11) seems to be much faster (also because they’re damn good hackers). I actually have ideas about improving the sampling result and this can lead to comparable performances. The thing is, inside a framework, the approach by BRS’11 may still be too complex to implement (they use very elegant techniques in their papers but not so easy to implement well, imho).

Yes, HyperANF seems like the right algorithm, but indeed, this probably requires a fair amount of 1337 h4x0r work to implement.

> Sampling can work, and I have a technical report about using sampling for this and other network measures.
> This is not surprising, as we know that by sampling we can approximate a probability distribution in the L1-norm with relatively few samples (there was a paper in ICTS’15 about this and much more).
> I can polish the TR a bit and send it to you in private, let me know.

Please do. It doesn’t have to be the fastest algorithm, just fast enough, and time spent on implementation is a factor.

Best,
Chris

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150902/d0283810/attachment.sig>


More information about the NetworKit mailing list