Archive for 10 listopada, 2013

10 listopada, 2013

k-hop reachability – opis problemu i analiza rozwiązania

- autor: tsissput
Opracował: Przemysław Grzędzielski 

1 Wstęp

Celem niniejszego wpisu jest przybliżenie czytelnikom problemu k-hop reachability, mającego duże znaczenie w szeregu dziedzin, które można zamodelować przy pomocy sieci (w szczególności w sieciach społecznościowych) oraz analiza rozwiązania tego problemu, zaproponowanego w artykule „K-Reach: Who is in Your Small World”.

 2 Opis problemu i jego znaczenie

 2.1 Sformułowanie problemu

 Dane wejściowe

Niech s (source) i t (target) oznaczają dwa wierchołki w grafie, modelującym sieć. Niech k jest pewną dodatnią liczbą całkowitą.

 Problem

Czy z wierzchołka s da się dojść do wierzchołka t w co najwyżej k krokach? Innymi słowy, czy istnieje ścieżka w grafie skierowanym od wierzchołka s do wierzchołka t o długości co nawyżej k?

 Dane wyjściowe

Jest to problem decyzyjny, więc wynikiem jest odpowiedź TAK lub NIE na postawione pytanie.

 2.2 Związki z innymi problemami grafowymi

Zauważmy, że klasyczny problem osiągalności wierzchołków, polegający na udzieleniu odpowiedzi na pytanie: czy wierzchołek t jest osiągalny z wierzchołka s (czyli, przykładowo – czy Jaś jest w jakiś sposób powiązany z Małgosią?), jest przypadkiem szczególnym przedstawionego problemu, w którym parametr k wynosi nieskończoność.

 2.3 Znaczenie w kontekście sieci społecznościowych

Nietrudno wyobrazić sobie, że problem ten ma potencjalnie duże znaczenie w kontekście sieci społecznościowych. Nierzadko bowiem nie wystarcza nam wiedza o tym, czy dwie osoby są ze sobią powiązane w ogóle (jak zauważają autorzy artykułu – dowolne dwie osoby najprawdopodobniej są w jakiś sposób ze sobą powiązane, biorąc pod uwagę słynne “twierdzenie” o six degrees of separation). Znacznie bardziej przydatna może okazać się wiedza o tym, czy dane dwie osoby są od siebie oddalone o pewną liczbę k, szczególnie w przypadku małych k.

Przykładowo: chcemy, aby szczegółowość informacji o profilu osoby A w portalu społecznościowym widziana przez osobę B zależała od tego, jak “blisko” w grafie znajdują się te osoby. Np. użytkownik A ustawił widoczność swoich danych teleadresowych w taki sposób, aby mieli do nich dostęp znajomi co najwyżej trzeciego stopnia. Kiedy użytkownik B wyświetla profil użytkownika A, potrzebujmy odpowiedzi na pytanie, czy użytkownik B jest “oddalony” od użytkownika A o nie więcej niż trzy.

 3 Przykładowe podejścia, ich wady i zalety

 3.1 Problem z Lady Gagą

Autorzy artykułu “K-Reach: Who is in Your Small World” dokonują istotnego spostrzeżenia: fakt, że wartość k jest mała (mniejsza od 6, bo takie instancje mają sens w kontekście rzeczonych six degrees) nie czyni problemu łatwiejszym. Wydawać by się mogło, że w takim wypadku sprawdziłoby się rozwiązanie naiwne, polegające na przejściu grafu wszerz (Breadth First Search) i sprawdzeniu, czy docelowa osoba zostanie napotkana w odległości nie większej niż k od wierzchołka początkowego. Problemem, który wskazują autorzy, jest obecność tzw. celebrities, czyli osób bardzo popularnych w całej sieci. Twierdzą oni, że w przypadku większości rzeczywistych zapytań na pewnym etapie przeszukiwania grafu napotkamy na celebrytę (nie przepadam za tym neologizmem…), który “zaprowadzi” nas do tak wielkiej liczby wierzchołków, że dalsze przeszukiwanie sieci stanie się zadaniem karkołomnym (przykład: Lady Gaga, która w chwili powstawania niniejszego wpisu ma 60 411 323 fanów na Facebooku – wyobraźmy sobie tę zajętość pamięciową!).

 3.2 DAG – Dlaczego Acykliczny Graf … ?!

Kolejne przytoczone przez autorów podejście opiera się na założeniu, że graf sieciowy jest acyklicznym grafem skierowanym (ang. Directed Acyclic Graph). W przypadku, kiedy tak nie jest (czyli – w rzeczywistości – praktycznie zawsze) zostaje on zredukowany do DAGa poprzez zastąpienie wszystkich silnie spójnych składowych (ang. strongly connected components) pojedynczymi wierzchołkami. Podejście to redukuje zajętość pamięciową i sprawdza się w przypadku pytania, czy połączenie między dwoma wierzchołkami w ogóle istnieje (wiadomo, że jeśli dojdziemy do wierzchołka zastępującego składową silnie spójną, to dojdziemy także do każdego z rzeczywistych wierzchołków ją tworzących). Zawodzi jednakże w przypadku rozważanego problemu k-reachability, ponieważ – jak nietrudno zauważyć – para wierzchołków “osiągalnych” nie musi być “k-osiągalna” (jeśli mogę pokusić się o spolszczenie nazwy naszego problemu).

Do powyższych spostrzeżeń dorzuciłbym jeszcze jedno, zasadnicze – w praktyce sieć społecznościową rzadko możemy w ogóle zamodelować w postaci grafu skierowanego, najczęściej bowiem “znajomość” między dwoma osobami jest relacją symetryczną, czyż nie?

 3.3 Najkrótsze ścieżki

Innym rozważanym podejściem jest stosowanie indeksów przeznaczonych do przetwarzania zapytań o najkrótsze ścieżki pomiędzy wierzchołkami w grafie. Użycie takiego indeksu, który danego wierzchołka s powie nam szybko (czyt. O(1)), jaka jest jego odległość od wierzchołka t, byłoby trywialne. Problemy, które wskazują autorzy, jest koszt przetwarzania zapytań o odległości między wierzchołkami oraz fakt, że indeksy takie przeważnie są tworzone dla grafów nieskierowanych.

Moim zdaniem, podstawowym mankamentem, który należałoby tutaj podkreślić, jest duża zajętość pamięciowa takiego indeksu oraz złożoność samego procesu tworzenia. Stworzenie macierzy najkrótszych odległości między wierzchołkami wymaga bowiem po prostu przejścia grafu w kolejności BFS (jeśli łuki mają jednakowe wagi, oczywiście). Jeśli natomiast łuki mają różne wagi, najkrótsze odległości między wierzchołkami na niewiele nam się przydadzą.

 4 Algorytm k-Reach

 4.1 Pokrycie wierzchołkowe

Zaproponowany algorytm konstruuje indeks, który pozwala na sprawdzenie, czy dane dwa wierzchołki leżą w odległości co najwyżej k. Do stworzenia indeksu wykorzystywane jest tzw. pokrycie wierzchołkowe grafu:

Pokrycie wierzchołkowe to taki podzbiór wierzchołków grafu G(V,E), że dowolna krawędź w tym grafie jest incydentna z co najmniej jednym wierzchołkiem tego podzbioru

Minimalne pokrycie wierzchołkowe to najmniejszy możliwy podzbiór wierzchołków grafu, który jest jego pokryciem wierzchołkowym

Problem znalezienia minimalnego pokrycia wierzchołkowego grafu jest NP-trudny. Istnieje jednak algorytm, który znajduje jego przybliżenie w czasie wielomianowym: 2-approximate minimum vertex cover.

Jego przebieg jest następujący (E oznacza zbiór krawędzi w grafie G, V zbiór wierzchołków w grafie G, S jest wynikowym zbiorem):

 S = <empty set>()
while (E is not empty){
(u,v) = randomly_select_edge_from_E
// add u and v to result set
S += u
S += v
// remove every edge that is incident to u or v
for every e : (e incident to u or v) {
E -= e
}
// remove u and v from the vertices
V -= u
V-=v
}
// S is the result
return S

Zauważmy, że dla każdej krawędzi (u,v), którą dodajemy do zbioru S, co najmniej jeden z pary wierzchołków musi należeć do minimalnego pokrycia wierzchołkowego (oznaczmy je jako C). W przeciwnym razie C nie spełniałoby definicji pokrycia wierzchołkowego (tzn. krawędź (u,v) nie byłaby incydentna z żadnym z wierzchołków należących do C). O skonstruowanym oszacowaniu możemy więc powiedzieć, że jego liczność jest co najwyżej dwa razy większa od liczności minimalnego pokrycia wierzchołkowego: |S| <=2*|C|.

 4.2 indeks k-Reach

Indeks k-Reach zakłada, że dane są:

• graf G(V,E)

• S – pokrycie wierzchołkowe grafu G

• parametr k

Indeks jest grafem I=(V_i, E_i, w_i) zdefiniowanym następująco:

• V_i = S

• E_i jest zbiorem krawędzi (u,v) należących do S takich, że v jest k-osiągalny z u (isReachable(u,v,k) == true)

• w_i to funkcja wagowa, która każdej krawędzi e=(u,v) ze zbioru E_i przyporządkowuje wagę (zauważmy, że isReachable(u,v,k-2) impikuje, że isReachable(u,v,k-1), co z kolei implikuje isReachable(u,v,k):

 – if (isReachable(u,v,k-2)) { w_i(e) = k-2;}
 – else if (isReachable(u,v,k-1)) { w_i(e) = k-1; }
 – else if (isReachable(u,v,k)) { w_i(e) = k;}

Procedura konstrukcji indeksu k-Reach jest następująca: dla każdego wierzchołka u w pokryciu S wyznaczamy zbiór S_k(u), zawierający wierzchołki znajdujące się w odległości nie większej niż k od niego, wykonując przejście BFS po grafie G). Pseudokod znajduje się poniżej:

S = 2-approximate_vertex_cover(G)
V_i = S
for each u in S {
S_k(u) = BFS(graph=G,upper_bound=k)
for each v in S_k(u) {
E_i += (u,v)
compute weight w_i for (u,v)
}
}
return I=(V_i,E_i,w_i)

 4.3 Przetwarzanie zapytań przy użyciu indeksu k-Reach

Zakładając, że dla danego parametru k skonstruowano indeks k-Reach (a także, uprzednio, pokrycie wierzchołkowe S), odpowiedź na pytanie: czy wierzchołek t jest oddalony od wierzchołka s o co najwyżej k, jest stosunkowo prosta. Istotne jest spostrzeżenie, że możemy tu mieć do czynienia z czterema przypadkami. Logika algorytmu jest prosta:

 Przypadek 1: s i t należą do S

Najprostszy przypadek. Jeśli zarówno s i t należą do pokrycia wierzchołkowego S, to isReachable(u,v,k) zachodzi wtedy i tylko wtedy, gdy krawędź (s,t) znajduje się w zbiorze krawędzi E_i naszego indeksu.

 Przypadek 2: s należy do S, t nie należy do S

Skoro t nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego poprzedniki należą do S (wynika to z definicji pokrycia wierzchołkowego). Wiadomo też, że jeden z tych poprzedników (o ile takie w ogóle istnieją) musi być (k-1)-osiągalny z wierzchołka s (wówczas docelowe t będzie k-osiągalne z wierzchołka s).

Przypadek 3: s nie należy do S, t należy do S

Sytuacja analogiczna do powyższej. Skoro s nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego następniki muszą należeć do S. Wiadomo też, że z co najmniej jednego z tych następników wierzchołek docelowy t jest (k-1)-osiągalny (wówczas jest on k-osiągalny z początkowego s).

 Przypadek 4: s, t nie należą do S

Rozumowanie podobne jak poprzednio. Wiemy, że wszystkie następniki s oraz wszystkie poprzedniki t należą do S. Sprawdzamy więc, czy istnieje taka para (u,v), że u jest następnikiem s, v jest poprzednikiem t oraz zachodzi isReachable(u,v,k-2). Jeśli taka para istnieje, to wiemy, że t jest osiągalny z s.

 4.4 Analiza złożoności

Warto zwrócić uwagę na złożoności obliczeniowe poszczególnych kroków prezentowanego algorytmu. Muszę przyznać, że wyjaśnienia podane przez autorów (dotyczy to w szczególności kroku nr 2) wydają mi się niekompletne, a co za tym idzie – niezrozumiałe.

 4.4.1 Tworzenie indeksu k-Reach

• Wyznaczanie pokrycia wierzchołkowego S: O(m+n)

• Tworzenie skierowanego, ważonego grafu I=(V_i, E_i, w_i): całkowita liczba wykonywanych kroków jest równa sumie kroków wymaganych do stworzenia zbiorów S_k dla każdego wierzchołka u (czyli zbiorów wierzchołków k-osiągalnych z u) – pamiętajmy, że w tym celu przechodzimy graf w porządku BFS dla każdego wierzchołka u (z maksymalnym zasięgiem k)

 4.4.2 Przetwarzanie zapytania dla danych s,t

Niech inDegree(u,G) i outDegree(u,G) oznaczają, odpowiednio, stopień wejściowy i stopień wyjściowy wierzchołka u w grafie G.

• Sprawdzenie, czy wierzchołek należy do V_i: O( 1 )

• Sprawdzenie, czy krawędź (u,v) należy do E_i i odczytanie jej wagi: O( log outDegree(u,I) ) lub O( log inDegree(v,I) ) przy założeniu, że graf jest przechowywany w formie listy sąsiedztwa (ang. adjacency list)

Na tej podstawie autorzy podają następujące złożoności przetwarzania poszczególnych przypadków zapytań wyróżnionych w algorytmie:

• Przypadek 1: O( log outDegree(s,I) )

• Przypadek 2: O( outDegree(s,I)+inDegree(t,G) )

• Przypadek 3: O( outDegree(s,G)+inDegree(t,I) )

• Przypadek 4: O(  sum_by_u_in_outNeighbours(s,G): (outDegree(u,I)+inDegree(t,G)) )

Uważam, że analizie złośoności obliczeniowej należałoby w artykule poświęcić nieco więcej miejsca. Co o nich sądzicie?

 5 Bibliografia

K-Reach: Who is in Your Small World”, 1 VIII 2012; James Cheng, Zechao Shang, Hong Cheng, Haixun Wang, Jeffrey X. Yu

10 listopada, 2013

Wprowadzenie do Linked Data

- autor: tsissput

Wstęp

Sieć WWW (World Wide Web) radykalnie zmieniła nasz sposób dzielenia się wiedzą poprzez obniżenie bariery w publikowaniu i dostępie do dokumentów w ramach globalnej przestrzeni informacji. Przeglądarki i linki hipertekstowe pozwalają użytkownikom na przeglądanie tej przestrzeni, a indeksowanie dokumentów i analiza struktur powiązań między nimi na wnioskowanie na temat potencjalnego znaczenia dla zapytania zadanego przez użytkownika. Jest to możliwe przez ogólny, otwarty i elastyczny charakter sieci, który jest postrzegany jako kluczowy element nieograniczonego wzrostu. Tradycyjnie dane publikowane w sieci były dostępne jako surowe wpisy w formatach CSV, XML lub oznaczone jako tabele HTML tracąc wiele z ich struktury oraz znaczenia. Konwencja hipertekstowych powiązań narzuca niejawny charakter relacji między powiązanymi dokumentami. Taki stan rzeczy uniemożliwia połączenie poszczególnych danych z określonego dokumentu z innymi powiązanymi danymi.

W ostatnich latach sieć ewoluowała z globalnej przestrzeni informacji powiązanych dokumentów w przestrzeń gdzie powiązane są zarówno dokumenty jak i dane. U podstaw tej ewolucji znalazł się zestaw najlepszych praktyk, w zakresie publikowania i łączenia danych strukturalnych, nazywany Linked Data. Zaadaptowanie zestawu najlepszych praktyk doprowadziło do rozszerzenia globalnej sieci połączonych danych o różne dziedziny, takie jak społeczeństwo, firmy, książki, publikacje naukowe, filmy, muzyka, programy telewizyjne i radiowe, genetyka, lekarstwa i próby medyczne, społeczności internetowe, statystyka i dane naukowe, opinie.

Ta sieć danych umożliwia powstanie nowego typu aplikacji. Istnieją ogólne przeglądarki powiązanych danych, które umożliwiają ich przeglądanie i nawigowanie pomiędzy źródłami wzdłuż połączeń między danymi. Są to mechanizmy przemierzające sieć powiązanych danych między różnymi źródłami umożliwiając wykonywanie ekspresyjnych zapytań o szerokich możliwościach na zagregowanych danych, podobnie jak dziś odbywa się to w lokalnych bazach danych. Sieć powiązanych danych otwiera też nowe możliwości dla aplikacji specjalizowanych. W przeciwieństwie do rozwiązań typu mashup 2.0 działających na stałym, określonym zbiorze źródeł aplikacje oparte na Linked Data działają na samej górze globalnej przestrzeni danych, co umożliwia dostarczenie wyczerpujących odpowiedzi.

Co to jest Linked Data?

graphSą to najlepsze praktyki na temat tworzenia w sieci powiązań pomiędzy danymi pochodzącymi z różnych źródeł. Dane mogą być tak różne jak bazy danych prowadzonych przez dwie organizacje w różnych lokalizacjach geograficznych lub systemy heterogeniczne w obrębie pewnej firmy, które trudno dopasować aby współpracowały na poziome danych. Technicznie Linked Data odnosi się do danych opublikowanych w sieci w taki sposób, że są one możliwe do odczytywania przez maszyny, a ich znaczenie jest wyraźnie określone, są związane z innym zewnętrznym zbiorem danych, a ten z kolei może być powiązany z kolejnym zewnętrznym źródłem.

Chociaż podstawową jednostką w sieci są dokumenty HTML połączone bez typowymi łączami, Linked Data opiera się na dokumentach zawierających dane w formacie RDF (Resource Description Framework), które przy pomocy wyrażeń łączą dowolne byty na świecie. Wynikiem tego jest nazywana przez nas sieć danych, którą można dokładnie określić jako sieć bytów na świecie opisanych przez dane w sieci.

Berners-Lee w 2006 roku przedstawił zestaw zasad publikowania danych w sieci w taki sposób, że wszystkie publikowane dane stają się częścią jednej globalnej przestrzeni danych:

  • Użyj URI jako nazwa bytu
  • Użyj http URI tak aby ludzie mogli wyszukać nazwy bytu
  • Gdy ktoś wyszukuje URI dostarcz użyteczne informacje przy pomocy standardów (RDF, SPARQL)
  • Zamieszczaj powiązania do innych URI tak aby można było znaleźć więcej informacji

Reguł te stały się znane jako ‚Linked Data principles’ i zapewniają podstawę dla publikowania i łączenia danych wykorzystując strukturę sieci Web zachowując jej architekturę i standardy.

Technologie wykorzystywane w Linked Data

Linked Data opiera się na dwóch technologiach, które są podstawą sieci WWW: URI (Uniform Resource Identifiers) i HTTP (HyperText Transfer Protocol). Chociaż URL (Uniform Resource Locator) stał się znany jako adres dokumentów i innych jednostek, które mogą znajdować się w sieci to URI zapewnia bardziej ogólny sposób rozpoznawania bytów, które istnieją na świecie. URI i HTTP są uzupełniającymi się technologiami i mają kluczowe znaczenie dla sieci danych – RDF. Podczas gdy HTTP zapewnia środki do konstrukcji i powiązania dokumentów w sieci WWW, RDF zapewnia ogólny, grafowy, oparty na danych model do konstrukcji i powiązania bytów opisujących rzeczywistość.

rdf_w3c_icon.128

Dla przykładu trójka RDF może stwierdzać, że dwie osoby A i B, każda identyfikowana przez URI, związane są faktem, że A zna B. Podobnie trójka RDF może wiązać osobę C z artykułem naukowym D w bibliograficznej bazie danych, stwierdzając, że C jest autorem D. Dwa zasoby powiązane w ten sposób można wyciągnąć z dwóch różnych zbiorów danych w sieci, dzięki czemu dane z jednego źródła są powiązane z danymi z innego źródła, tworząc w ten sposób sieć danych. W ten sposób możliwe jest, że trójka RDF łączy dwa różne zbiory danych analogicznie jak link łączy dokumenty w sieci Web.

RDF Vocabulary Definition Language (RDFS) i Web Ontology Language (OWL) stanowią podstawę do tworzenia słowników, które mogą być używane do opisania bytów występujących w rzeczywistości i opisu związków występujących między nimi. Słownictwo jest zbiorem klas i właściwości. Słowniki same są wyrażone za pomocą RDF, używając RDFS i OWL, które zapewniają różne stopnie ekspresyjności w modelowaniu domeny zainteresowania. Każdy może opublikować słownik w sieci danych, które z kolei mogą być powiązane przy mocy trójek RDF w taki sposób, że klasy i własności z jednego słownika są powiązane z innymi, wyrażają w ten sposób mapowania pomiędzy powiązanymi słownikami.

Przez zastosowanie URI do określania zasobów, HTTP jako mechanizmu wyszukiwania i RDF jako reprezentacja opisu zasobów, Linked Data bezpośrednio opiera się na ogólnej architekturze sieci Web. Sieć danych może więc być postrzegana jako dodatkowa warstwa, która ściśle przeplata się z klasyczną siecią dokumentów i ma wiele tych samych właściwości:

  • Sieć danych jest ogólna i może zawierać dane dowolnego typu.
  • Każdy może publikować dane.
  • Wydawcy danych nie są ograniczeni w wyborze słowników do opisu reprezentacji danych.
  • Byty są połączone przez RDF tworząc globalny graf danych, który obejmuje źródła danych i pozwala na odkrywanie nowych źródeł danych.

Z punktu tworzenia aplikacji sieć danych ma następujące cechy:

  • Dane są ściśle oddzielone od formatowania i graficznej reprezentacji.
  • Dane są samo opisujące. Jeśli aplikacja wykorzystująca Linked Data napotka na dane opisane nieznanym słownictwem aplikacja może odwołać się do URI, które identyfikują wykorzystane słownictwo w celu znalezienia ich definicji.
  • Zastosowanie HTTP jako standardowego mechanizmu dostępu do danych i RDF jako standardowego modelu danych upraszcza dostęp do danych w stosunku do sieci Web, która opiera się na różnorodnych modelach danych i interfejsach dostępowych.
  • Sieć danych jest otwarta, co oznacza, że aplikacje nie muszą nie muszą mieć ściśle określonego zestawu źródeł danych ale w czasie wykonywania programu można odkrywać nowe źródła danych za pomocą powiązań RDF.

Podsumowanie

Rozwinięcie globalnej sieci danych opartej na technologiach podstawowych dla obecnej sieci WWW oraz otwartość tego rozwiązania ułatwia wprowadzenie Linked Data w życie. Nowe aplikacje bazujące na tej technologii mogą korzystać z niezliczonej ilości źródeł danych, które to nie muszą być definiowane w trakcje wytwarzania oprogramowania. Zastosowana przez Linked Data reprezentacja danych umożliwia bezpośrednie ich przetwarzanie przez maszyny. Możliwe staje się nawigowanie wzdłuż połączeń między danymi, niezależnie od źródeł ich pochodzenia. Linked Data może okazać się rewolucyjnym rozwiązaniem propagującym Semantic Web i przyspieszającym ewolucję Web 2.0 do Web 3.0.

Christian Bizer, Tom Heath, & Tim Berners-Lee (2009). Linked Data – The story so far International Journal on Semantic Web and Information Systems DOI: 10.4018/jswis.2009081901

Autor: Łukasz Grzybowski