jump to navigation

The Advisor czyli koniec bibliografii 08/31/2012

Posted by Mikołaj Morzy in konferencja, nauka, sieci społeczne.
trackback

W trakcie tegorocznej konferencji ASONAM wysłuchałem ciekawej prezentacji pt. „Fast Recommendation on Bibliographic Networks” wygłoszonej przez Onura Kucuktunca z Ohio State University. Idea polega na przyspieszeniu algorytmu rekomendującego artykuły naukowe na podstawie historycznej bazy bibliograficznej. Główny algorytm rekomendacyjny to losowy spacer z restartem (RWR, ang. random walk with restart), autorzy niestety nie podają źródła dla bazy danych cytatów. Idea algorytmu jest prosta: rozpoczynając od wskazanego artykułu naukowego A podążaj losowo do artykułów cytujących artykuł A lub prac cytowanych przez A. W zależności od dodatkowego parametru algorytmu losowy spacer może mieć preferencję do prac starszych lub nowszych. Unikanie pułapki zapętlenia odbywa się przez losowy przeskok do innego artykułu. Z czysto naukowego punktu widzenia interesujące są zaproponowane optymalizacje: po pierwsze autorzy sugerują przeorganizowanie macierzy sąsiedztwa opisującej graf cytowań w taki sposób, aby losowy spacer unikał cache misses, czyli żeby kolejne bloki danych wymagane przez algorytm znajdowały się już w pamięci podręcznej (tzw. lokalność odwołań do pamięci). Po drugie, autorzy wprowadzają do algorytmu z pozoru niewielkie poprawki, które ponad sześciokrotnie redukują liczbę aktualizacji pozycji w macierzy sąsiedztwa. W efekcie uzyskują ogromne przyspieszenie działania algorytmu.

A teraz najciekwasze.

Algorytm został zaimplementowany w prototypowym systemie theadvisor, dostępnym w postaci usługi webowej. System przyjmuje na wejście plik Bibtex lub RIS z częściową bibliografią, a w odpowiedzi wyrzuca rekomendowaną listę pozycji literaturowych. Podane na wejście pozycje stanowią ziarno (ang. seed) od którego algorytm rekomendacyjny zaczyna przeszukiwanie bazy danych bibliograficznych. Nie posiadając plliku Bibtex lub RIS można także podać nazwisko autora lub nazwę obszaru (oczywiście kosztem trafności rekomendacji). Jakby tego było mało, theadvisor wyświetla rekomendowaną listę prac oraz dostarcza wizualizacji powiązań między publikacjami.

Załóżmy, że pracuję nad artykułem dotyczącym ewolucji sieci społecznościowych w czasie. Rozpocząłem od zdefiniowania prac „Graphs over time: densification laws, shrinking diameters and possible explanations” i „Graph evolution: Densification and shrinking diameters” Leskoveca, Kleinberga i Faloutsosa jako moich głównych inspiracji. Następnie ustawiam suwak „I want papers to be more…” pośrodku między opcjami „traditional” i „recent” i klikam na przycisk „Start the search with the selected papers”.  Odpowiedź theadvisor jest następująca:

Relevant Citations

  1. Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos:
    On Power-law Relationships of the Internet Topology.
    SIGCOMM, pp.251-262, 1999. [dblp] [citeseer] [pdf] [google]
  2. Hongwu Ma, An-Ping Zeng:
    The Connectivity Structure, Giant Strong Component and Centrality of Metabolic Networks.
    Bioinformatics, 19(11):1423-1430, 2003. [dblp] [arXiv] [citeseer] [pdf] [google]
  3. Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
    The Web as a Graph: Measurements, Models, and Methods.
    COCOON, pp.1-17, 1999. [dblp] [citeseer] [pdf] [google]
  4. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan D. Sivakumar, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal:
    Stochastic Models for the Web Graph
    [citeseer] [pdf] [google]
  5. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
    Trawling the Web for Emerging Cyber-Communities.
    Computer Networks, 31(11-16):1481-1493, 1999. [dblp] [citeseer] [pdf] [google]
  6. Michael Mitzenmacher:
    A Brief History of Generative Models for Power Law and Lognormal Distributions.
    Internet Mathematics, 1(2), 2003. [dblp] [citeseer] [pdf] [google]
  7. P. Erdős, A Rényi:
    On the Evolution of Random Graphs
    1960. [citeseer] [pdf] [google]
  8. Jon M. Kleinberg:
    Authoritative Sources in a Hyperlinked Environment.
    J. ACM, 46(5):604-632, 1999. [dblp] [citeseer] [pdf] [google]
  9. Fan R. K. Chung, Linyuan Lu, Van H. Vu:
    The Spectra of Random Graphs with Given Expected Degrees.
    Internet Mathematics, 1(3), 2003. [dblp] [citeseer] [pdf] [google]
  10. Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos:
    R-MAT: A Recursive Model for Graph Mining.
    SDM, 2004. [dblp] [citeseer] [pdf] [google]

A na dodatek jeszcze to:

Visualization of bibliographic database

Wiele wskazuje na to, że przez najbliższy czas kompilowanie referencji do artykułów stanie się dużo łatwiejsze. Cały prototyp jest dostępny pod adresem theadvisor.osu.edu

Komentarze»

No comments yet — be the first.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: