Zachowywanie prywatności w sieciach społecznościowych

Z pewnością każdy z nas zauważył, że sieci społecznościowe wdarły się szturmem do naszego życia i z uwagi na swoją ogromną popularność nieprędko z niego znikną. W 2013 roku blisko77 90% polskich internautów korzystało z serwisów społecznościowych (dane firmy badawczej Gemius). Co więcej, około 12% pracodawców przyznaje się do przeglądania facebookowych profili kandydatów na stanowisko przed ich zatrudnieniem (dane z roku 2007!). Wraz ze wzrostem popularności serwisów typu Facebook, Twitter, Youtube, coraz większa waga przykładana jest (i słusznie!) do zachowywania prywatności w sieciach społecznościowych.

Żeby dokładnie zrozumieć poruszane w niniejszej notce zagadnienia wprowadzimy model sieci społecznościowej w postaci grafu, w którym wierzchołki odnoszą się do użytkowników, natomiast krawędzie do relacji pomiędzy nimi. Gdy mówimy o prywatności w takiej sieci, musimy uwzględnić wiele aspektów, między innymi:

• istnienie użytkownika w sieci – jeśli osoba postronna (nazwijmy ją atakującym) dowie się, że dany użytkownik jest w konkretnej sieci (np. sieci reprezentującej milionerów), prywatność zostanie naruszona,
• parametry wierzchołka takie jak np. jego stopień – jeśli atakujący odkryje ilość połączeń danego użytkownika, może dowiedzieć się o jego priorytecie w sieci,
• połączenie z inną jednostką sieci – np. podczas transakcji finansowej gdy dwa wierzchołki mają połączenie gdy nastąpiła wymiana środków – również narusza prywatność,
• wrażliwe dane, które mogą być przypięte do użytkownika (np. ciężka choroba).

Aby móc myśleć o zachowaniu prywatności w sieci, należy wiedzieć w jaki sposób są one „atakowane”. Wyróżniamy ataki aktywne – takie, w których do ataku używane są nowe wierzchołki wprowadzane do sieci, które dołączają się do starych wierzchołków oraz ataki pasywne, w których nie są dodawane ani wierzchołki, ani krawędzie. Atakujący najczęściej zanim zdobędzie poufne dane konkretnego użytkownika musi znać jego otoczenie – wiedza o sąsiadujących wierzchołkach, znajomość topologii mogą wiele „pomóc” atakującemu. Aby utrudnić atakującemu identyfikację konkretnego wierzchołka wprowadza się tzw. anonimizację danych. Jak sama nazwa wskazuje, służy ona po to, by zachować anonimowość poprzez „wystawienie” na zewnątrz sieci z takimi wierzchołkami, aby niemożliwe było ich rozróżnienie.

K-­anonimizacja (K-anonymity)

K­anonimizacja polega na „zaciemnianiu” niektórych danych, aby istniało co najmniej K – 1 węzłów, które będą takie same, a co za tym idzie nierozróżnialne, anonimowe. Innymi słowy nie ma możliwości, aby w sieci istniał jakiś jeden niepowtarzalny wierzchołek (np. gdyby zawierał nr telefonu komórkowego i byśmy nie „zaciemnili” tego numeru – byłoby to niemożliwe). Poniżej przykład 2­anonimizacji. Oryginalna tabela przedstawiająca wierzchołki w sieci:

Po 2-­anonimizacji ta sama tabela będzie wyglądała następująco:

W anonimizacji dąży się do tego, aby żaden z obiektów nie wskazywał na konkretny podmiot/przedmiot w sposób jednoznaczny. Ciekawostka: aby jednoznacznie zidentyfikować 87% obywateli USA, „wystarczy” znać datę urodzenia, płeć oraz kod pocztowy.

K­anonimizacja nie musi dotyczyć wyłącznie samych danych – może również dotyczyć np. stopnia wierzchołka (K­degree anonymity). Efekt działania tej anonimizacji jest następujący: dla każdego wierzchołka uzyskujemy co najmniej K – 1 wierzchołków o tym samym stopniu. Nigdy nie będzie sytuacji, że jakiś wierzchołek będzie miał unikatową liczbę połączeń z innymi wierzchołkami. Wykonywane jest to przez algorytm odpowiednio dodający fałszywe i usuwający prawdziwe krawędzie. Empiryczne badania pokazały, że można zachować topologiczną użyteczność grafu zaspokajając założenia K­stopniowej anonimizacji.

Oprócz tych dwóch K­anonimizacji istnieje również K­anonimizacja sąsiadów (K­neighbourhood anonymity), która z kolei wymaga, aby dla wierzchołka istniało K – 1 innych wierzchołków, dla których podgraf bezpośrednich sąsiadów będzie izomorficzny z podgrafem bezpośrednich sąsiadów ów wierzchołka. Innymi słowy – aby w sieci nie istniał żaden wierzchołek o unikatowym zestawie najbliższych sasiadów.

Anonimizacja poprzez losowość

Losowe dodawanie/usuwanie elementów grafu jest kolejną często stosowaną strategią zachowywania prywatności w sieciach. W tej strategii poprzez wprowadzanie fałszywego szumu utrudniamy odczytywanie i eksplorację sieci przez atakującego. Dodatkowo możemy zachowywać niektóre własności grafu np. poprzez dodanie wierzchołkowi k losowych relacji do innych wierzchołków oraz usunięcie k losowych relacji od „starych” wierzchołków zawsze zachowujemy stopień wierzchołka.

Jeśli z n wierzchołków zrobilibyśmy macierz A o wymiarach n * n i uzupełnili wewnątrz pola: 1 – jeśli między wierzchołkiem, który odpowiada wierszowi, a wierzchołkiem, który odpowiada kolumnie jest relacja oraz 0 – gdy relacji nie ma, to wynik procesu anonimizacji poprzez losowość przedstawilibyśmy jako sumę macierzy A + E, gdzie macierz E byłaby „macierzą mieszania”. W macierzy E mielibyśmy wartości +1, jeśli krawędź między odpowiadającymi wierzchołkami została dodana, oraz ­1, gdy usunięta.

Przykład:

Macierz wynikowa:

Widać, że w „zafałszowanej” macierzy wynikowej połączenia są inne, natomiast mając „macierz mieszania” jesteśmy w stanie łatwo powrócić do macierzy oryginalnej.

Anonimizacja przez generalizację

W odróżnieniu od K­anonimizacji oraz anonimizacji przez losowość, które modyfikowały strukturę grafu (dodawały/usuwały krawędzie), anonimizacja przez generalizację polega na grupowaniu wierzchołków w klastry (albo grupowaniu relacji), w których można odpowiednio ukryć wrażliwe dane. Najlepszym przykładem może być przedział wiekowy, do którego „wrzucimy” wierzchołek, a w którym już znajdują się inne wierzchołki. Podczas generalizacji niestety musimy się liczyć z utratą części danych lub precyzji – np. zamiast wieku 24 mamy przedział wiekowy (na przykład <20; 40>).

Efektem generalizacji mógłby być np. graf złożony z superwierzchołków zawierających co najmniej K „zwykłych” wierzchołków, a pomiędzy superwierzchołkami byłyby superrelacje, czyli krawędzie pomiędzy superwierzchołkami o wadze równej ilości połączeń między wierzchołkami z dwóch stron superrelacji. Generalizacja jest skutecznym sposobem na anonimizację, aczkolwiek stosowanym w przypadku gdy możemy sobie pozwolić na utratę precyzji.

Przykład generalizacji można przedstawić na znanej już tabeli:

Po generalizacji oraz dodatkowym „zaciemnieniu” innych danych mamy:

Metody zachowywania prywatności w sieciach społecznościowych są wciąż w początkowym stadium (porównując np. do danych tabularnych). Wynika to przede wszystkim z tego, że są one znacznie bardziej skomplikowane, dlatego też zachowanie w nich anonimowości jest większym wyzwaniem. Natomiast można się spodziewać szybkiego rozwoju tej dziedziny ze względu na coraz większe zapotrzebowanie na ochronę danych, które „wystawione są” w serwisach już codziennego użytku.

Nie wyobrażam sobie dalszego rozwoju serwisów społecznościowych bez usprawniania ochrony danych w nich przechowywanych. Chociaż w tej chwili zadziwiająco duży odsetek użytkowników korzystających z najpopularniejszych z serwisów nie wydaje się być zainteresowany zachowywaniem prywatności myślę i mam nadzieję, że w najbliższej przyszłości to się zmieni. Aby tak było wraz z rozwijaniem technologii konieczne jest rozwijanie również świadomości użytkowników i ich wiedzy na temat niebezpieczeństw związanych ze zdradzaniem zbyt wielu informacji o sobie w serwisach, w których „żyją”.

Źródła:

Kliknij, aby uzyskać dostęp pgnet_111013_1.pdf

Kliknij, aby uzyskać dostęp SocialNetworkAnonymization_survey.pdf

Kliknij, aby uzyskać dostęp ppsn.pdf

Kliki Politechniki

Introduction:

The goal is to visualize PUT Computer Science Institute scientist according to their publications, who they make publications with, when they make it etc. We had only wide-audience available data and such was used. Document is structured as follows:

1. In process section one can find information how the experiment was conducted.
2. Statistical data sections gives some insights on quantitative measures of PUT scientists and publications.
3. Finally Visualization section presents result graphs of scientists.

Process:

We decided to obtain data from google scholar for obvious reasons. Unfortunately no real API exists what would make our task much easier. Eventually we ended up parsing HTML with open source Python library. Unfortunately like quite a few libraries which had been tested before it was not working properly and we needed to introduce a few improvements.

In program we create graph in which each author corresponds to a node and each edge represents a fact of being co-author of the same article. Weight of such edge is number of citations and additional attributes are title and publish date. Additionally nodes, apart from name, contain information about total number of publications and citations as well as scientific degree and division within faculty of computer science the scientist work for. Data format is suitable to be imported to Gephi but also easely adjusted to other formats.

Statistical data:

In total we analyzed about 80 scientists out of total 120 due to their absence on google scholar. Here are some interesting charts (click on picture to see it in full size):

Scientific degrees and number of dempartment employees pie charts

Total number of publications and citations per division

Total citations of each article

Total number of citations per author

Total number of publications per author

Visualization:

Here we go with visualization of the data. We’ve used Python formatted csv files imported to Gephi. Mind that authors (nodes), have proper number of citations and publications but edges (being co-author of the same article) are created exclusively by articles made by at least two Poznań Univeristy of Technology workers (it still gives meaningful results but reader has to be aware it).

1. Who is the most cited scientist from PUT? MostCited – labels
2.  Who has the biggest number of publications? Full – publications
3. Graph divided to clusters and then colored by Modularity Class pretty much visualizes CS subdivisions (real existing ones) Modularity Class – labels
4. How far are you from Jan Węglarz? JW Heat Map according to common publications JW Heat
5. You may also want to check Mikołaj Morzy MM Heat and Agnieszka Ławrynowicz AL Heat new heat maps
6. Who has the biggest betweenness measure? Simple: Betweeness
7. Last, but not least: who has the biggest number of PUT Publications-friends: Degree labels

Thanks for reading!

Authors: 100376 , 98436, 98758

Linked data

W dzisiejszych czasach prawie każdy posiada komputer z dostępem do Internetu. Każdy kto przegląda sieć, szukając informacji, czytając artykuły wykorzystuje linked data. Mechanizm ten wykorzystuje Semantic Web którego celem jest połączenie różnych danych.  Obecnie nasze komputery bez naszej pomocy nic by same nie zrobiły, to my kierujemy nimi wskazując im poprawną drogę, dzięki nam wykorzystują swoją siłę – bez nas były by tylko blaszaną puszką. Linked data umożliwia powstanie nowych aplikacji. Obecnie istniejące przeglądarki powiązanych danych, umożliwiają przeglądanie i wyszukiwanie między źródłami wzdłuż połączeń między danymi. Mechanizmy te przeszukują sieć powiązanych danych między wieloma źródłami, dzięki czemu możliwe jest wykonanie ekspresyjnych zapytań o wielkich możliwościach w bazach danych.

Linked data to najefektywniejsze metody na temat tworzenia rozwiązań między danymi pochodzącymi z różnych źródeł w sieci. Przedstawione dane mogą być zróżnicowane tak jak bazy danych z różnych organizacji. Linked data można nazwać systemem który łączy precyzyjnie dane i wiarygodne źródła.

Dzieje się tak za pomocą:

– odnośników URI

– składni RDF

 

Odnośniki URI czyli Universal Resource Identifier to internetowym standardem który pozwala rozpoznać zasoby w sieci. Z reguły jest to duża ilość znaków, zapisana według standardów. Przykładem jest URL, który wskazuje także metodę dostępu.

Składnia URI wygląda następująco:

-wzór skrócony hierarchiczny zaczyna się od ukośnika / np :// przykładem może być link do strony http://www.wikipedia.org

<schemat> : <część hierarchiczna> [ ? <zapytanie> ] [ # <fragment> ]

-wzór skrócony niehierarchiczny, występuje tylko dwukropek : przykład mailto:jakas-osoba@wikipedia.org

URI odnoszą się do konkretnych ludzi, zdarzeń ale także pojęć, można je również wykorzystywać do poznania danych z dysku naszego komputera, różnego rodzaju notatek, kontaktów, wiadomości czy plików. Podsumowując pojęcie URI jest narzędziem do identyfikacji ogółu.

Kolejny aspekt to odnośniki RDF – metody które pozwalają na przedstawienie zasobów sieci Web, oparte są na XML głównym ich zadaniem jest wyświetlenie informacji zawartych w sieci w taki sposób aby były łatwo zrozumiałe dla komputerów. Celem odnośników RDF jest stworzenie standardu zapisu danych o danych, w których nie było by chaosu jak w znacznikach <meta>. Pozwoliło by to na automatyczne przetwarzanie treści i jednocześnie umożliwiło by łatwiejsze poszukiwanie informacji oraz śledzenie danych na interesujący nas temat.

Linked Open Data oraz semantic web stają się coraz popularniejsze, co za tym idzie coraz więcej ludzi stara się mieć swój wkład w tej dziedzinie. Liczba entuzjastów rośnie bardzo szybko, a sami zainteresowani tym tematem starają się wprowadzić coraz to lepsze metody uzyskania dostępu do danych. Ponad to osoby zaangażowane w projekt Linked Data robią wszystko co mogą aby udostępnić publicznie dostęp do danych, które są w obecnych czasach zamknięte przez rządy czy służby, myślę że szczególnie zainteresowanie miałyby dane dotyczące nauk ścisłych. Materiały w Linked Data stale rosną, a razem z nimi liczba wiarygodnych danych.

 

 

Bibliografia

http://pl.wikipedia.org/wiki/Uniform_Resource_Identifier

http://www.archiwistyka.pl/artykuly/artykuly_i_felietony/530

http://pl.wikipedia.org/wiki/Resource_Description_Framework

http://www.w3.org/standards/semanticweb/data

Autor 119919

Esy floresy i fantasmagorie sieciowo społecznościowe

Tak naprawdę powinienem zamieścić w niniejszym artykule wyłącznie odnośniki oraz gorąco zachęcić do zapoznania się z nimi wierząc w ciekawość i zaangażowanie wnikliwego czytelnika. Podejrzewam jednak, iż byłoby to naiwne i zbyt optymistyczne. Dlatego też postaram się przybliżyć najciekawiej jak umiem kilka kwestii bez prób dowodzenia czegokolwiek, lekko jedynie muskając powierzchnię tematów, co mam nadzieję zachęci do dalszej lektury.

Gdybyśmy chcieli przeprowadzić kampanię reklamową lub promocyjną na różnorodnych serwisach społecznościowych potrzebowalibyśmy lajków, retweetów lub innej adekwatnej dla danego serwisu rzeczy. Optymalnie potrzebowalibyśmy dotrzeć do osób które się zaangażują, ale umiejętne nabijanie statystyk jest równie potrzebne. W tym celu moglibyśmy kupić lajki czy retweety na jednym z wielu serwisów wybierając ostrożnie ten sprawdzony i nie przesadzając z rozmachem. Obawy odnośnie ich skuteczności są uzasadnione ale spokojne, ich portfolio nierzadko zawiera bardziej skomplikowane przedsięwzięcia jak sprawieniem by dana aplikacja była w top 10 Apple Store w danej kategorii – wszystko jest możliwe. Czytając na temat omawianych procederów można natrafić skrajne opinie w zależności od tego kto sponsorował publikację. Kilka ciekawszych linków odnośnie powyższego:

• http://www.buycheapfollowersfast.com/facebook/
• http://blog.wishpond.com/post/74283886668/should-you-buy-facebook-likes
• http://www.businessinsider.com/fake-twitter-followers-test-2012-8

Jako informatycy możemy zechcieć zrobić coś sami i szczerze nie jest to specjalnie trudne lecz tylko do pewnej skali. Wiadomo, że na wszystko możemy mieć autorskie rozwiązania ale posilając się tym co już jest w sieci weryfikację emailem rozwiązują takie serwisy jak http://10minutemail.com/10MinuteMail/index.html nieco bardziej uciążliwą telefoniczną http://www.burnerapp.com/ a najcięższą captchę http://www.deathbycaptcha.com/user/login Innym zagadnieniem jak szybko blokowany numer IP (nawet przy VPN) poradzimy sobie klasycznymi serwerami proxy (Tor byłoby lekko mówiąc niemądry). I tak można by wymieniać dalej tylko pytanie po co?

Oficjalne zdanie facebooka jest oczywiste https://www.facebook.com/help/281084665319172  – zakaz, tylko jest jeden problem. Kupienie reklamy na facebooku skutkuje także lajkami od botów broniących się przed wykryciem i jest w efekcie nie tak skuteczne. Więcej o tym w arcyciekawym filmie do którego obejrzenia gorąco zachęcam https://www.youtube.com/watch?v=oVfHeWTKjag

Pozwolę sobie poruszyć kilka mniej technicznych aspektów.

Serwisy społecznościowe mimo całego swojego dobrodziejstwa jak wszystko w nadmiarze szkodzą. Problemem jest tylko to, że w ich przypadku znacznie ciężej dostrzec szkodliwość niż chociażby papierosów. Nie chodzi tu o bycie „złodziejem czasu”, gdyż przecież leniwi i tak zawsze znajda sposób na zabicie produktywności, a pozostali wyciągną nieproporcjonalnie większe korzyści.

Śmieszy mnie gdy ktoś jest gotów wyśmiać tych mniej ambitnych za śledzenie losów bohaterów telenowel i życia gwiazd nie dostrzegają, że śledzenie facebookowych statusów czy tweetów dalekich znajomych jest prawie tym samym. Realnie nasi bliżsi znajomi to około 150 osób, a reszta to szum i nierzadko w przypadku spotkania na ulicy nawet nie przystaniemy. Zainteresowanie tym co w ich życiu słychać jest tylko pozornie bardziej uzasadnione niż w przypadku bohaterów telenowel. Są oczywiście liczne wyjątki ale nie mówmy o ekstremach. Idąc dalej nawet jak kogoś znamy nie uchronimy się przed tym, że na facebooku może zachowywać się lekko to ujmując niestandardowo. Na przykład opisuje swoje życie w szczegółach, dzieli się dosłownie wszystkim, spostrzegawczo zauważających, że strasznie pada czy stale wrzuca zdjęcia swoich dzieci czy chrześniaka. (Lista jest długa i dla jej dopełnienia warto zajrzeć tutaj: https://www.facebook.com/notes/cheesy-pick-up-lines/the-12-most-annoying-types-of-facebookers/136478482496)

Mam taki obraz w głowie gdy ktoś nagrywa przedstawienie swoich dzieci i wrzuca je na facebooka. Znajomi natychmiast opatrzą je komentarzami pełnymi zachwytu. Problem tylko w tym, że gdyby po 5 sekundach była tam cokolwiek innego nikt tego nawet nie zauważy. Komentujący nie obejrzeli filmu do końca, pewnie nawet nie zaczęli bo szczerze po co? Dlaczego kogoś miałby obchodzić cudze dzieci skoro nawet sam rodzic wolał je nagrywać niż rzeczywiście oglądać w najlepszej możliwej rozdzielczości i nagłośnieniu? Takie przykłady można mnożyć.

Ciekawym jest także efekt psychologiczny. Wielu z nas ma w znajomych podróżników, którzy non stop zaznaczą w jakim miejscu na świecie byli i w jakim hotelu nie spali, wraz z kolegą którego życie składa się z imprez i trzeźwienia oraz pary chwalącej się każdą wspólną kolacją i romantycznym uniesieniem. W serwisach społecznościowych ludzie przedstawiają najlepsza wersje siebie i dzielą się najciekawszymi wydarzeniami z życia. Oczywistym jest, że w każdej chwili kiedy Ty się uczysz, nudzisz w domu czy masz obowiązki pracęe etc. ktoś się doskonale bawi, zwiedza świat i kogoś poznaje. Tak się działo przecież stale, ale nigdy jeszcze nie było tak realne i namacalne. Łatwo zaakceptować i nas to nie rusza, że taki gwiazdor to ma życie, ale nie najbliżsi znajomi. W świetle powyższego nie martwiłbym się tu eskalacją zazdrości lecz depresji, dlatego znajomość i przemyślenie niektórych zjawisk może nam służyć.

Nie rozumiem konsumowania serwowanej papki w mediach i tak samo jest w przypadku informacji z serwisów społecznościowych. Czy wystarczy zawierzyć algorytmom serwującym nam treści i decydujących co mamy zobaczyć? Osobiście nie wyobrażam sobie używania facebooka bez skonfigurowania listy bliskich znajomych i sprecyzowania jakie rodzaje notyfikacji chcę otrzymywać. Nawet mimo tych zabiegów mówię, mało!.

Ostatnio kolega zamieścił film z treningiem wdzięczącej się modelki którego reprezentacyjne ujęcie nie było stosowne do pojawienia się w pracy czy na uczelni, z kolei inny stwierdził, że podzieli się obrazkiem z serwisu który regularnie przeglądam, oraz wiadomością z dzisiejszej gazety. Nie wpominając o tym, że co chwile aplikacje moich znajomych publikują za nich bo obiecano im, że zobaczą kto odwiedził ich profil. Pytam się za jakie grzechy ja to muszę oglądać i ubolewam, że personalizacja jest tak ograniczona i dostosowana do w dalszym ciągu statystycznego „Nowaka”.

Sygnalizowałem wielokrotnie i pisałem feedback na facebooku do autorów za pomocą zamieszconego tam formularza, jednak albo nie dostawałem odpowiedzi albo nie dopatrzyli się naruszeń regulaminu, nie mają czasu etc.

Powstało kilka prób personalizowania treści jednak są to niedojrzałe projekty. Jednym z bardziej popularnych pomysłów są wtyczki do Chroma i Mozilli typu „nie lubię”, ale szczerze nie zdają egzaminu. Ostatecznie w tym szumie nawet po oczyszczeniu i zgłębieniu tematu ciężko się odnaleźć. Pozostaje nadzieja, że autorzy serwisów poprawią coś w tych kwestiach. Wspominane wtyczki:

• https://addons.mozilla.org/en-us/firefox/addon/facebook-dislike/
• https://chrome.google.com/webstore/detail/fb-dislike/lpekolbadenjphaaapbgdienjjpgbali

Na zakończenie pragnę podkreślić, że nie zachęcam do zabawy w sztuczne konta i farmy lajków i proponuję korzystanie z formularza na facebooku za pomocą którego można pomóc autorom serwisu go ulepszać https://www.facebook.com/help/127103474099499/ z którego jak wspomniałem wielokrotnie sam korzystałem i opisywałem możliwe nadużycia. Niedawno także zaaplikowałem do Facebooka i może uda mi się trochę im pomóc 🙂

W razie kontaktu chęci kontaktu proszę pisać na mojego gmaila appogeum

98758

Platforma VIVO – sposób na Ontologie internetową

Z uwagi na szybki rozwój technologii , aby podejść do wyzwań
i problemów badawczych , wymagana jest w większym stopniu współpraca
zespołów specjalistów z różnych dziedzin i instytucji , aby wspólnymi
siłami wypracować innowacyjne rozwiązania w trakcie prowadzonych prac,
minimalizować niepowodzenia i w optymalny sposób wykorzystywać sukcesy
oraz rozpowszechniać zdobytą wiedzę.

Jednym ze sposóbów jest wykorzystanie platformy VIVO ;
semantycznej, sieciowej aplikacji o otwartym kodzie źródłowym ,
zaprojektowanej  aby ułatwiać wyszukiwanie informacji o realizowanych
badaniach , stypendiach , naukowcach, i wspierać tworzenie sieci badawczych.

Technologia VIVO

VIVO to aplikacja zbudowana na technologii Semantic Web ,
łączy Ontologie internetową i instancje edytora ,
zawartość narzędzia integracyjnego i lekki system zarządzania treścią.

Ontologia rdzenia VIVO zapewnia framework do modelowania naukowcom
i ich działalności w sposób spójny.

Zawartość VIVO zapewnia opiekunom systemu zarządzania witryną ,
dodatkową kontrolę nad architekturą informacji
i funkcje wyświetlania, jak również branding.
VIVO jest implementowany jako aplikacja sieci web Java,
a wersje VIVO są zaprojektowane do pracy z Apache Tomcat ( servlet cointainer ).

VIVO obsługuje ontologie OWL,
które są reprezentowane w systemie przy starcie jako modele obiektów Jena.
Ontologie te mogą być opracowane z wykorzystaniem na zewnętrznym edytorze,
jak na przykład Protégé , lub mogą być rozwijane w samej VIVO.

Podstawowe zasady VIVO

• Open software
• Open data
• Open ontology
• Open community
• Zdecentralizowanie infrastruktury – sterowanie lokalne

Jakie zadania pełni VIVO?

• Integracja danych z wielu źródeł

– Systemy rekordu

– Raportowanie aktywności – Wydział

– Zewnętrzne źródła (np, Scopus, PubMed, NIH Reporter)

• Zapewnia interfejs przeglądu i edycji

Krótka chatakteryztyka działania :

Gdy dane są dostępne, VIVO tworzy publiczną stronę internetową,
z stronami pokazującymi profil informacyjny,
przynależności do osób fizycznych i członkostwo,
powiązania oraz inne informacje dla jednostek organizacyjnych.

 

Wyświetlanie informacji jest tematem pełni napędzanym konfigurowalnie.
Informacje serwisu są indeksowane przy użyciu Lucene
do tworzenia wybranych wniosków z dostępnych danych.
Poziom wnioskowania może być wybrany w konfiguracji VIVO.
VIVO obsługuje uwierzytelnianie samodzielnej edycji
podzbioru informacji o osobie.
Pozwala to, na przykład – wydziału przesyłać obrazy,
nawiązanie do osobistych danych i projektów stron internetowych,
oraz dostarczenie oświadczeń badań lub listy zainteresowań badawczych.
Autoryzacja może być poprzez Shibboleth ,
a strona jest w pełni przeszukiwana.

ONTOLOGIA VIVO

Rozwój ontologii VIVO następuje w czterech zasadach:
1. • Rdzeń i lokalizacja:
Konstrukcja rdzenia VIVO i lokalizacji łączy zalety
standaryzacji.
2. • Modularny projekt:
Wyróżnia się niezależny system
lecz połączone moduły, mogą być
stosowane w różnych kontekstach,
aby umożliwić wiele funkcji.
3. • Wyrównywanie z innymi ontologii:
Ontologia VIVO dostosowuje się do innych ontologii.
4. • Modelowanie złożonych relacji jako klas:
W ontologii VIVO, złożone relacje są modelowane
jako jednostki, w celu dodania właściwości tych związków.

Przykład ontologii pokazuje koncepcje mapy VIVO w wersji 1.3 czyli główne klasy i obiektywne właściwości.

Bąbelki w różnych kolorach reprezentują różne źródła klas.
Linie między bąbelkami wskazują ich związki, które są właściwościami obiektu w ontologii VIVO.

 

Interoperacyjność

Kluczową kwestią w budowaniu ontologii VIVO
jest umożliwienie interoperacyjności pomiędzy różnymi ontologiami.
Ontologia interoperacyjności jest kluczowym czynnikiem
niezbędnym do ujednolicenia
i integracji rozproszonych zasobów ontologii poprzez Internet.

Istnieją różnorodne działania związane z projektem VIVO,
podkreślając agencje federalne, instytucje akademickie,
stowarzyszenia zawodowe, na zysk wydawców i dostawców danych,
jak również dokonanie wielu starań w sieci semantycznej i ontologii w rozwoju społeczności.

Główni Partnerzy to :
CASRAI (Consortium Advancing Standards in Research Administration Information)
EuroCRIS ( Current Research Information Systems)
ORCID (Open Researcher and Contributor ID )

 

Odwołując się do podsumowania blogu
autora Dominika Piotrowskiego – który nawiązał do VIVO
jako semantyczna baza wiedzy , można powiedzieć że
„ silne dane i inteligentne aplikacje internetowe mogą wspierać
partnerstwo pomiędzy instytucjami i tym samym zwiększyć
możliwości ponownego wykorzystania zgromadzonych danych ”,
a zachętą jest aby „ polskie biblioteki akademickie
mogłyby przyjrzeć się bliżej temu semantycznemu narzędziu,
celem wsparcia swoich instytucji macierzystych ”.

 

+++ Bibliografia +++

http://www.vivoweb.org

http://www.ideals.illinois.edu/bitstream/handle/2142/42085/460.pdf?sequence=2

http://www.semanticweb.com/symplectic-takes-another-step-helping-universities-engage-research-collaboration-discovery_b44557#more-44557

http://www.cmswbibliotekach.umk.pl/baza-wiedzy/vivo-czyli-semantyczna-baza-wiedzy/

=========================

Wojtek-Beniamin Wolski [ 119972 ]

=========================

Nowa jakość w odkrywaniu społeczności w grafach

Wstęp

Jako, że wiele systemów i zjawisk we współczesnym (i nie tylko) świecie przyjmuje postać sieci lub zbiorów wierzchołków połączonych ze sobą  niezwykle interesujące są różne właściwości przez nie prezentowane oraz możliwość ich automatycznego odnajdywania.

Przykłady sieci:

– sieci społecznościowe

– sieci znajomości

– sieci współpracowników

– sieci technologiczne

– sieci biologiczne (takie jak na przykład układ nerwowy)

Większość z ostatnich prac na ten temat skupiała się na wielu statystycznych wskaźnikach, które owe sieci dzielą między sobą.

Są to przede wszystkim:

– efekt małego świata

– prawo potęgowe stopni wierzchołków

– klastrowanie

– skłonność tworzenia małych społeczności

Klastrowanie przedstawia bardzo ciekawą własność sieci społecznościowych oznaczającą, że dwójka znajomych jednej osoby ma znacznie większe prawdopodobieństwo znania się wzajemnie niż dwie losowo wybrane osoby z populacji.

C=3x liczba trójkątów w grafie/liczba połączonych trójek.

Prawdopodobieństwo wystąpienia takiego zdarzenia jest określone przez C. W Grafie pełnym wynosi 1, a w sieciach naturalnych zazwyczaj waha się od 0,1 do 0,5.

Skłonność tworzenia małych społeczności oznacza tendencję tworzenia się zbiorów wierzchołków stosunkowo gęsto połączonych, które są luźno połączone pomiędzy sobą. Ta własność jest bez wątpienia mocno sprzężona z klastrowaniem, jednakże z punktu widzenia analizy danych stanowi osobne wyzwanie.

Tradycyjna metoda

Hierarchiczny algorytm klastrowania wykrywania społeczności zakłada obliczenie wagi (bliskości) dla każdej pary Wij. Następnie bierzemy n wierzchołków bez połączeń pomiędzy nimi i dodajemy połączenia pomiędzy parami w kolejności malejących wag. W rezultacie otrzymujemy zagłębione zbiory coraz większych komponentów. Niestety proponowane wagi bliskości tak jak inne rozwiązania hierarchicznego algorytmu klastrowania mają wiele wad, między innymi pozostawianie pojedynczych wierzchołków (z małymi wagami) poza społecznościami.

Przekład drzewa klastrów

Pośredniość Wierzchołków

Panowie Newman i Girvan zaproponowali zmianę podejścia do wykrywania społeczności: zamiast poszukiwać wierzchołków, które są najbardziej centralne dla społeczności, postanowili poszukać tych,  które są najmniej centralne – które leżą najbardziej pomiędzy społecznościami. Graf wynikowy jest konstruowany przez stopniowe usuwanie wierzchołków z oryginalnego grafu zamiast, jak poprzednio dodawanie najsilniejszych.

Zaproponowano uogólnienie pośredniości Freemana na krawędzie – krawędź otrzymuje pośredniość w podobny sposób jak wierzchołki – jak sumę najkrótszych ścieżek przebiegających przez nią.

Proponowany algorytm ma następującą postać:

1. Oblicz pośredniość dla wszystkich krawędzi w grafie
2. Usuń krawędź z najwyższą pośredniością
3. Oblicz ponownie pośredniość w grafie – uwzględniając usunięcie krawędzi
4. Wracaj do kroku 2, aż żadne krawędzie nie pozostaną w grafie.

Złożoność algorytmu:

Do obliczenia pośredniości wykorzystywany jest algorytm Newmana działający w czasie O(mn). Musi zostać powtórzony m razy (dla każdej usuwanej krawędzi), tak więc ostateczna złożoność wynosi O(m^2 n).

Przy optymalizowaniu czasu działania może pojawić się pokusa nie obliczania ponownie pośredniości, jednakże taka strategia okaże się błędna dla dwóch społeczności połączonych więcej niż jedną krawędzią – mamy gwarancję, że tylko jedna z nich będzie miała wysoką miarę pośredniości od samego początku.

Testowanie metody:

Metoda została przetestowana na różnych sieciach. Wygenerowanych komputerowo, przez co zapewniających określone właściwości, jak i sieciach występujących naturalnie. Dla wszystkich w tych sieci znana była struktura połączeń społeczności. Wyniki działania algorytmu były zadowalające – algorytm poprawnie rozpoznawał połączenia.

Grafy generowane komputerowo

Na potrzeby testów przygotowano duży zestaw grafów składających się ze 128 wierzchołków. Każdy graf był podzielony na cztery społeczności (po 32 wierzchołki). Krawędzie były umieszczane w grafie losowo z prawdopodobieństwem Pin pomiędzy wierzchołkami z tej samej społeczności oraz Pout dla wierzchołków pomiędzy społecznościami. Oczywiście Pin>Pout, a ich stosunkiem możemy sterować gęstością połączeń w społeczności. Sumaryczne prawdopodobieństwo było ustalone tak, aby stopień wierzchołków był średnio równy 16.

Algorytm sprawdza się dobrze dla Zout (połączenia poza społeczność) jest mniejsze od 6 (a tym samym Zout większe od 10) klasyfikując ponad 90% wierzchołków prawidłowo. Dla Zout większe niż 6 jakość klasyfikacji drastycznie spada, co jest logiczne, gdyż liczba połączeń wewnątrz społeczności zbliża się do tej z poza społeczności, co sprawia, że podział na społeczności jest mocno niejasny. Wyniki tego algorytmu zdecydowanie przewyższają wyniki jakościowe hierarchicznego algorytmy klastrowania.

Porównanie wyników nowego algorytmu vs. algorytmu hierarchicznego klastrowania. Kółka – nowy algorytm, kwadraty – algorytm hierarchicznego klastrowania

Sztuczne a prawdziwe środowisko

W oczywisty sposób testowanie algorytmu na sztucznych sieciach jest wygodne, gdyż możemy kontrolować ilość i rodzaj połączeń, tworząc tym samym bardzo jednoznaczne sieci, jednakże prawdziwie użyteczny algorytm może okazać się tylko na naturalnie występujących sieciach, dlatego panowie Girvan i Newman wykorzystali kilka przykładów z życia codziennego (i badań), aby sprawdzić jakość wykrywania połączeń w społecznościach.

Badanie klubu karate Zachary (Zachary’s Karate Club Study)

Zachary  obserwował 34 członków klubu karate przez okres 2 lat. Podczas obserwacji administrator i trener klubu pokłócili się, w wyniku czego trener odszedł z klubu i założył swój własny zabierając ze sobą około połowy obecnych członków. Zachary konstruował sieć znajomości pomiędzy członkami klubu używając różnych miar do zobrazowania przyjaźni pomiędzy jednostkami. Na potrzeby testu algorytmu wykorzystana zostanie zwykła, nieważona wersja grafu przyjaźni. Algorytm wyodrębnił dwie społeczności zaczynając od węzła 1 i 34 (odpowiednio trener i administrator klubu), które prawie idealnie odzwierciedlały realny podział klubu po odejściu trenera.

Podział klubu karate na społeczności względem trenera i administratora

Hierarchiczny algorytm klastrowania, dla porównania również z sukcesem wyodrębnił osobne społeczności, jednakże korelacja pomiędzy właściwym rozpadem klubu a efektem działania tego algorytmu była znacznie mniejsza.

Football amerykański (College Football)

Następnie algorytm został przetestowany na drużynach futbolu amerykańskiego. Wierzchołki reprezentowały zespoły a krawędzie regularne gry pomiędzy zespołami w sezonie 2000′. Struktura społeczności jest znana, gdyż zespoły połączone są w konferencje zawierające po 8-12 zespołów każda i gry są częstsze wśród członków jednej konferencji.[W sezonie 2000′ średnio 7 gier wewnątrz i 4 gry poza konferencją dla zespołu]

Algorytm poprawie klasyfikował większość przypadków. Błędy pojawiły się tam, gdzie drużyny grały podobną ilość meczów przeciwko drużyną z własnej konferencji i obcej. [Niektóre były podzielone]

Taki wynik jest spodziewany – jest to sytuacja podobna do tej, kiedy w grafach wygenerowanych komputerowo Zin zbliżało się do Zout i bez dodatkowych informacji nie dało się odróżnić społeczności.

Wnioski i komentarze

Metoda wydaje się być ciekawa i bardzo efektywna zarówno dla odkrywania znanych struktur (opisane powyżej) jak  i nieznanych pomagających zrozumieć pewne zjawiska (odsyłam do oryginału).

Pewnym problemem może być wydajność. Czas działania O(m^2 n) jest problematyczny dla bardzo dużych grafów i należałoby znaleźć pewne usprawnienia. Błędy popełniane przez algorytm całkowicie mieszczą się w wynikach oczekiwanych, gdyż obserwując zjawiska jedynie przez krótki okres czasu i nie posiadając dodatkowej wiedzy my jako ludzie również nie bylibyśmy w stanie wyodrębnić pewnych społeczności – tych w którymi algorytm miał problem.

Po usprawnieniach wydajnościowych algorytm może okazać się bardzo użyteczny dla odkrywania społeczności.

Bibliografia

Girvan, Newman Community structure in social and
biological networks Cornell University, University of Michigan 2001

Krzysztof Lewiński

98436

Rewolucja, czy zwykła zmiana – Semantic Web w oczach użytkowników Internetu

Streszczenie

Celem niniejszego opracowania jest zbadanie podejścia użytkowników do zmian jakie wynikają z zastosowania Semanic web i nazwania ich mianem Web 3.0. Sprawdzenie jak w ich oczach będą wyglądały zmiany, które od kilku lat są skutecznie rozwijane. Celami szczegółowymi są też: konfrontacja użytkowników z osobami na co dzień zajmujących się branżą IT i nowymi technologiami, co do nadchodzących zmian; porównanie spojrzeń na kwestie techniczne obu stron; a także zbadanie poziomu zadowolenia z tego co aktualnie istnieje. Dzięki temu możliwe będzie porównanie i ocena jak do proponowanej zmiany odnoszą się przeciętni użytkownicy, a jak ludzie, którzy na co dzień wykorzystują, a nawet tworzą Internet.

Krótkie spojrzenie na problem prognozowania połączeń w sieciach społecznościowych z wykorzystaniem miar opartych na modelu grafowym

Wprowadzenie:

Podczas nazywanej przez Samuela Smitha Wiekiem Sieci, pierwszej epoki trzeciego tysiąclecia, zaobserwować można było niezwykły wzrost skupienia życia społecznego, politycznego, a nawet ekonomicznego wokół sieci tworzonych w Internecie. Ewolucja ta stopniowo doprowadziła do wzrostu zainteresowania tematem sieci społecznościowych, aż w końcu sprawiła, iż dla wielu ludzi stały się one nieodłącznym punktem życia, ułatwiającym komunikację na masową skalę.

Sieć społecznościowa w ogólności definiuje jednostki oraz połączenia realizowane między nimi poprzez współzależności, takie jak: przyjaźń, wspólne interesy, współpraca, zainteresowania, wiedza, czy przekonania. Jako naturalny przykład sieci społecznościowej przedstawić można grupę naukowców prowadzących badania w danej dziedzinie, gdzie połączenia pomiędzy dwoma osobami występują w przypadku, gdy prowadziły one wspólne badania lub były współautorami prac naukowych.

Warto pamiętać, iż wbrew przekonaniu wielu osób, sieci społecznościowe to nie tylko popularne serwisy typu: Facebook, Twitter, czy LinkedIn, ale również portale takie jak: Wikipedia, Slashdot, czy Epinions, które to, ze względu na możliwość nawiązywania zarówno pozytywnych, jak i negatywnych połączeń, wynikających chociażby z odmiennych przekonań czy niezgodności opinii, określane są jako „Signed Social Network”. Jako inny przykład sieci społecznościowej przytoczyć można strukturę  sieci web, a dokładniej zestaw linków pomiędzy stronami domowymi.

Link-prediction:

Rozwój sieci społecznościowych następuje niezwykle dynamicznie, a ich wzrost oraz topologia zmieniają się w znaczący sposób w niewielkich odstępach czasu. Jakkolwiek niewykonalnym jest prognozowanie nowych jednostek pojawiających się w sieci, istnieje możliwość przewidywania połączeń pomiędzy już istniejącymi indywidualnościami.

Formalnie definiując problem, można stwierdzić, iż mając obraz sieci w chwili t, poszukiwane są z jak największym prawdopodobieństwem jednostki, pomiędzy którymi powstaną powiązania w sieci w przedziale czasowym t do t’.

Rozwiązanie problemu prognozowania połączeń oparte jest na cechach obiektu oraz istniejących już połączeniach, dlatego też najczęściej podczas przewidywania połączeń wykorzystywane są różnego rodzaju miary podobieństwa, a samo zagadnienie zajmuje szeroki obszar zainteresowań w zakresie eksploracji danych, w którym to wiele zadań przetwarzania danych wykorzystuje relacje pomiędzy obiektami. Upraszczając, zadanie prognozowania połączeń zdefiniowane może zostać jako binarny problem klasyfikacji.

Ze względu na wspomniany już dynamiczny rozwój sieci, a także na ich niejednokrotne stosunkowo duże rozrzucenie, osiągnięcie wysokiej precyzji oceny staje się dużym wyzwaniem. Możliwość zastosowania problemu również w innych dziedzinach, takich jak: bibliografie, biologia molekularna, systemy rekomendacyjne, czy policyjne śledztwa, determinuje jednakże powstawanie oraz rozwój wielu algorytmów umożliwiających przewidywanie połączeń.

Matematyczny opis problemu:

Jednym z najpowszechniejszych, a jednocześnie jednym z najwcześniej powstałych, modeli wykorzystywanych w prognozowaniu połączeń w sieciach społecznościowych jest model oparty na teorii grafów, stosowany również w badaniach prowadzonych przez Davida Libena-Nowella oraz Jona Kleinberga, amerykańskich naukowców znanych z prowadzonych badań nad algorytmami wykorzystywanymi w sieci.

Wykorzystując teorię grafów, sieć społecznościowa przyrównana może zostać do grafu postaci G=<V,E >, w którym każda krawędź e=u,v∈E  reprezentuje połączenie pomiędzy wierzchołkami u  oraz v , mające miejsce w danej jednostce czasowej t . Wierzchołki natomiast odpowiadają poszczególnym jednostkom sieci. Model ten jest grafem nieskierowanym, wobec czego zaobserwować można tożsamość pomiędzy zbiorami u,v  oraz v,u .

W modelu grafowym problem prognozowania połączeń sprowadza się do oszacowania prawdopodobieństwa z jakim do grafu, w zadanym przedziale czasowym (t,t’) , zostaną dodane odpowiednie krawędzie.

Wielokrotne związki pomiędzy wierzchołkami u i v opisane mogą być jako krawędzie równoległe, oznaczone różnymi znacznikami czasowymi.

Model grafowy jest modelem uniwersalnym, co implikuje możliwość przeprowadzenia na nim popularnych metod klasyfikacji, wykorzystując przykładowo naiwny klasyfikator Bayesa, sieci neuronowe, SVM, czy też metodę k-najbliższych sąsiadów. Celem wykonania klasyfikacji należy jednak wcześniej dokonać odpowiedniego wyboru zestawu cech, na których to koncentrują się wspomniane algorytmy.

Miary prognozowania:

Algorytmy grafowe głównie skupiają się na obliczeniach związanych z miarą podobieństwa opartą na sąsiedztwie wierzchołków lub zestawie połączeń pomiędzy dwoma wierzchołkami. Jakkolwiek niewątpliwą zaletą przetwarzania tego typu jest ogólność miary, możliwość jej zastosowania dla różnych przypadków, a także brak konieczności posiadania wiedzy dziedzinowej, w przypadku dużych sieci może pojawić się problem związany z dużymi kosztami obliczeniowymi.

Node Based Topological Patterns:

W przypadku algorytmów opartych na analizie sąsiedztwa wierzchołków, istnieje wiele metod wyznaczania wagi połączenia pomiędzy wierzchołkami, oznaczanej jako score(x,y) . Niezależnie od wykorzystanego sposobu, przyjęta została nomenklatura, w której zbiór sąsiadów wierzchołka x  w grafie oznaczony jest przy pomocy symbolu Γ(x) . Miary oparte są na idei zakładającej, że prawdopodobieństwo powstania połączenia pomiędzy dwoma wierzchołkami jest tym większe, im większa jest część wspólna pomiędzy ich zbiorami sąsiadów. Przekładając powyższe na problem analizy sieci, można powiedzieć, że szansa współpracy pomiędzy dwoma autorami rośnie wraz z liczbą wspólnych publikacji pomiędzy ich znajomymi.

• Common neighbors:

Miara oparta bezpośrednio na liczbie wspólnych sąsiadów pomiędzy dwoma wierzchołkami. Generalizując, jeśli wierzchołek x jest połączony z wierzchołkiem y , a wierzchołek y  jest połączony w wierzchołkiem z , istnieje wysokie prawdopodobieństwo wystąpienia w przyszłości połączenia pomiędzy wierzchołkiem x oraz z .

• Jaccard coefficient:

Podejście bazujące na metodzie common neighbors, wprowadzając do niej czynnik normalizacyjny. W związku z powyższym, w przypadku większej liczby wspólnych znajomych, prawdopodobieństwo wystąpienia połączenia powinno rosnąć. Zgodnie jednak z badaniami Libena-Nowella, wydajność współczynnika Jacarda jest znacznie gorsza niż miary common neighbors.

• Adamic/Adar:

Miara wykorzystująca współczynnik wagowy, przypisywany w przypadku wystąpienia połączenia z wierzchołkami charakteryzującymi się  małym stopniem.

• Preferential attachment:

Metoda mająca swoje podwaliny w założeniu, że prawdopodobieństwo powstania nowego połączeniu jest proporcjonalne do korelacji zbiorów sąsiadów dla wierzchołków x oraz y, co oznacza, że im większy jest zbiór sąsiadów wierzchołka x , tym większa szansa, że nowa krawędź będzie wychodzić z tego wierzchołka.

Path based Topological Patterns:

Path based Topological Patterns to metody oparte na wyznaczaniu zbioru najkrótszych ścieżek pomiędzy dwoma wierzchołkami na podstawie zestawu wszystkich ścieżek łączących te wierzchołki.

• Shortest Path Distance:

Metoda opierająca się na twierdzeniu, że im krótsza ścieżka dzieli dwa wierzchołki, tym wyższe jest prawdopodobieństwo wystąpienia połączenia pomiędzy nimi.

• Katz:

Miara sumująca bezpośrednio zestaw ścieżek łączących dwa wierzchołki, przypisując odpowiednią wagę ścieżkom w zależności od ich długości.

• Hitting time:

Metoda oparta na losowym iteracyjnym przejściu od wierzchołka x  do y . Miara Hitting time (Hx,y)  odpowiada czasowi wykonania przejścia, czyli liczbie niezbędnych do wykonania kroków. Im krótszy czas przejścia, tym wyższe jest prawdopodobieństwo wystąpienia połączenia pomiędzy dwoma wierzchołkami.

• Rooted PageRank:

Jak odkrył Chung Zhao, algorytm PageRank wykorzystywany do tworzenia rankingów stron internetowych, jest nieodłącznie związany z metodą Hitting time, co sprawia, iż algorytm ten, poddany pewnym modyfikacjom, może również być używany w problemie przewidywania połączeń. W takim przypadku podobieństwo dwóch wierzchołków opierane jest na prawdopodobieństwie losowego powrotu od wierzchołka y do wierzchołka x.

• SimRank:

Podejście oparte na definicji, iż pomiędzy dwoma wierzchołkami jest szansa na powstanie połączenia, jeśli są one związane z podobnymi sąsiadami.

Higher-level approaches:

Algorytmy „Meta-approaches” mogą być używane w połączeniu z każdą z metod przedstawionych powyżej.

• Low-rank approximation:

Low-rank approximation jest problemem minimalizacji, gdzie funkcja kosztu mierzy dopasowanie pomiędzy grafem zadanym, a grafem otrzymanym w wyniku wybrania podzbioru grafu, najlepiej aproksymującego model wyjściowy. Ranking może być tworzony z wykorzystaniem metod takich jak miara Katz, czy metoda wspólnych sąsiadów.

• Unseen bigrams:

Problem prognozowania połączeń zbliżony jest do problemu estymowania częstotliwości w tak zwanych „unseen bigrams”. Zgodnie z tą metodą, miara poprawnej estymacji wystąpienia połączenia dla wierzchołków x,y może zostać zwiększona poprzez wykorzystanie miary dla wierzchołków z,y, wiedząc, że wierzchołek x jest podobny do wierzchołka z. Miara wyznaczona może być poprzez dowolną z metod zaprezentowanych powyżej.

• Clustering :

Jakość wykonywanych estymacji poprawiana może być poprzez usunięcie mniej istotnych krawędzi z wykorzystaniem procedury grupowania, a następnie uruchomienie metod predykcji na „wyczyszczonych” podgrafach.

Porównanie

Konfrontując w swoich badaniach działanie przedstawionych powyżej metod, Jon Kleinberg i Dawid Liben-Nowell, zbadali podobieństwo otrzymywanych przy ich pomocy wyników. Rezultat zaprezentowany został w tabeli 1.

Analizując przedstawione dane, zaobserwować można podobieństwo pomiędzy estymacją dokonywaną przy pomocy metod Katz, Adamic/Adar oraz Low-Rank. Podobnie, analogie widoczne są również w działaniu miar Rooted PageRank, SimRank oraz Jaccard. Podejściem dającym rezultaty zdecydowanie odbiegające od pozostałych jest metoda Hitting time.
Niezależnie jednak od zastosowanej metody, należy zwrócić uwagę na fakt, iż wykonane estymacje cechuje dość niski poziom poprawności, co widoczne jest na podstawie danych zawartych w tabeli 2.

Konkluzje
Opisane powyżej przybliżenia pozwalają skupić się na różnych miarach podobieństwa opartych na topologii grafu. W większości przypadków, zadanie prognozowania połączeń sprowadza się jedynie do problemu istnienia połączenia. Zadanie to może stać się jednak bazą do rozwiązania pozostałych problemów, związanych ze znaczeniem połączeń, ich siłą oraz liczbą.
Zważając na fakt popularności oraz dynamiczności wzrostu sieci społecznościowych, zrozumienie mechanizmu, zgodnie z którym następuje ich rozwój, jest niezwykle istotne i może przynieść wiele korzyści. Przykładowo w serwisach społecznościowych typu Facebook, czy Twitter, przewidywanie połączeń wykorzystywane jest w celu polepszenia systemu sugerowania nawiązywania kontaktów. Odchodząc od popularnych portali, problem prognozowania połączeń może zostać wykorzystany również do automatycznego kreowania linków, budowania systemów rekomendacyjnych, uzupełniania i tworzenia bibliografii, jako pomoc dla badaczy w poszukiwaniu ekspertów oraz dokumentacji związanych z danym obszarem zainteresowań, a nawet do identyfikowania grup przestępczych. Niezwykle ciekawym zastosowaniem przewidywania połączeń może być zastosowanie go w ramach realizacji projektów grupowych, gdzie organizacje mogą posłużyć się odpowiednimi metodami formując bardziej efektywne grupy.
Jakkolwiek zaprezentowane miary cechuje niska trafność przewidywania, z powodzeniem mogą one zostać wykorzystane w bardziej zaawansowanych algorytmach klasyfikacji.

Źródła:

Kliknij, aby uzyskać dostęp link-pred.pdf

Kliknij, aby uzyskać dostęp SNDA11.pdf

Opracowała: Joanna Skotarczyk

David Liben-Nowell, & Jon Kleinberg (2003). The Link Prediction Problem for Social Networks Journal of the American society for information science and technology DOI: 10.1002/asi.20591

Graph Search, czyli semantyczna wyszukiwarka Facebooka.

Graph Search – wyszukiwanie w socjogramie jako trzeci filar Facebooka.

Pierwszy filar to nasza nieśmiertelna ściana z wiadomościami (News Feed). Drugi – wprowadzona pod koniec 2011 roku oś czasu (Timeline).

Wyszukiwarka — bo tym właśnie z punktu widzenia użytkownika będzie Graph Search — ma pomóc odkryć coś nowego lub usprawnić poruszanie się na Facebooku.

Graph Search ma mieć mnóstwo zastosowań. Będzie można znaleźć na przykład wszystkie osoby, które mieszkają w jakimś mieście i lubią jakąś aktywność. Dzięki temu można będzie bez odrywania oczu od serwisu odkryć coś nowego, przede wszystkim nowych znajomych, na przykład znajomych naszych znajomych, z którymi mamy szansę się spotkać i mamy coś wspólnego. Ułatwi to też trafienie do popularnej wśród pewnych grup restauracji lub polecanego przez znajomych dentysty.

Facebook rozrasta się – codziennie dochodzą nowi użytkownicy, a starzy dorzucają nowe lajki, zdjęcia, linki i komentarze. Baza informacji rośnie w niesłychanym tempie. Do tej pory jednak nie było zbytniej możliwości przeszukiwania jej przez użytkowników. W efekcie Facebook jest nastawiony bardzo na to, co dzieje się „teraz” – większość osób jest przykuta do swojego strumienia aktualności, nie wychodzi poza niego. Powód jest prosty – znalezienie czegoś na Facebooku starszego niż kilka tygodni, szczególnie jeśli nie dotyczy jednej osoby i nie jest zdjęciem, jest strasznie wkurzające.

Graph Search upraszczając – jest to wyszukiwarka, która pozwala przeszukiwać bazy Facebooka. Ale to uproszczenie, porównanie do zwykłej wyszukiwarki, byłoby (szczególnie zdaniem Marka Zuckerberga) bardzo krzywdzące. Rozbijmy więc nowość na kilka punktów:

1. Uprzedzając wszelkie wątpliwości, Zuckerberg na samym początku powiedział, że użytkownicy mogą przeszukiwać jedynie te rzeczy, które zostały im udostępnione. Do tej pory bowiem wiele rzeczy było zbyt starych, żeby je wygrzebać. Teraz łatwiej będzie je znaleźć.

2. Graph Search nie opiera się o słowa kluczowe, jak robi to np. wyszukiwarka Google’a. Facebook, szczególnie w fazie beta Socjogramu, bardziej polega na elementach w swojej bazie danych – użytkownikach, fanowskich stronach czy wpisanych zainteresowaniach – i ich powiązaniach ze sobą. Dlatego jeśli będziemy szukać znajomych, którzy lubią Grę o tron, Graph Search poinformuje nas przede wszystkim o osobach, które polubiły taką stronę, a nie o tych, które gdzieś tam wspomniały o „tronie” i „grze” w jednym poście. W efekcie co prawda silnik wyszukiwania może pominąć część wartościowych informacji, odsiewa jednak wiele śmieciowych wyników.

3. Całość działa w oparciu o frazy. „Znajomi, którzy lubią…”, „Zdjęcia ze mną i …”, „Restauracje w pobliżu … lubiane przez znajomych z kraju …”, a nawet „singielki mieszkające w … i interesujące się …” – łączy się to z poprzednim punktem. Znowu, tak skonstruowane wyszukiwanie jest nieco ograniczające i może pomijać niektóre informacje, docelowo jednak ma szansę zapewnić znacznie bardziej wartościowe wyniki. Pytanie, czy się to nie zmieni w miarę rozwoju usługi i jej wychodzenia z fazy bety.

4. Całość jest zintegrowana ze stroną główną. Główna belka serwisu została całkowicie zdominowana przez pasek wyszukiwania, podczas gdy ikonki notyfikacji oraz ustawienia zostały zepchnięte do prawej strony. Wpisywane w pole frazy dynamicznie zmieniają stronę. Z punktu widzenia użytkownika to istotna cecha serwisu – upraszcza cały proces.

Graph Search ma umożliwić użytkownikowi przeszukiwanie zapisów aktywności własnej i znajomych. Będzie więc można poprosić o listę zdjęć, które użytkownik polubił, listę zdjęć konkretnych znajomych zrobionych w wybranym mieście 5 lat temu, listę zespołów, których słuchają współpracownicy, listę miast, w których mamy rodzinę i tak dalej. Na razie można zapisać się do zamkniętych testów wyszukiwarki, które prowadzone będą w tylko języku angielskim. Graph Search ma ponadto szanować ustawienia prywatności użytkowników.

Facebook chce, aby dzięki temu wyszukiwaniu życie było łatwiejsze, a świat mniejszy. Możliwe, że jest ot kolejny sposób aby użytkownicy Facebooka nie rezygnowali z serwisu, a chętniej z niego korzystali oraz pojawiali się także nowi internauci. Wall Street Journal przekazał informację, że zmniejsza się zainteresowanie Facebookiem. Analiza dotyczyła Stanów Zjednoczonych, gdzie w grudniu z serwisu przestało korzystać (czyli w ciągu miesiąca wcale go nie odwiedziło) 1,4 miliona użytkowników. W sumie używa go jeszcze ponad 167 milionów Amerykanów, ale strata jest spora i cieszy zwłaszcza w kontekście wiadomości z poniedziałku, kiedy to Guardian powiadomił, że z serwisu Zuckerberga uciekło 600 tysięcy Brytyjczyków z ponad 33 milionów, a w tym miesiącu nie zalogowało się już kolejnych 300 tysięcy. Statystyki można znaleźć na stronie czeskiej firmy SocialBakers.

Według tych samych danych, w Polsce w ciągu ostatniego miesiąca aktywnych użytkowników Facebooka przybyło prawie 400 tysięcy (171 tysięcy w ciągu ostatnich dwóch tygodni). W sumie korzysta z niego lekko ponad 10 milionów Polaków, co daje nam 23 pozycję na Świecie (z 212 monitorowanych państw). W ogólnym rozrachunku liczba użytkowników serwisu nadal rośnie i nieubłaganie zbliża się do symbolicznej granicy miliarda. W niektórych krajach użytkowników Facebook już znudził. Według analityków przytłaczające są reklamy, promowane posty i ciągłe zmiany. Pole do rozwoju nadal jednak jest — głównie w krajach Azji, gdzie z szacowanych 4 miliardów mieszkańców Facebooka używa zaledwie 7%.

Decyzja o masowym przejściu na nowy silnik zapadła w Palo Altro w lipcu 2013, a pierwszymi królikami doświadczalnymi są amerykańscy użytkownicy. Usługa została uruchomiona na kilkuset milionach kont. Zmiana jakościowa będzie ogromna. Jeśli jednak pamiętacie przepychanki ze słynną osią czasu – nie wszystkim przypadnie do gustu, bo nie wszyscy kochają super hiper mega innowacje.

Nowa funkcja jest na razie w Polsce jeszcze nie aktywna. Na tej stronie możemy się zapisać na listę oczekującą – choć część materiałów o Socjogramie (tak będzie się usługa nazywać w Polsce) została zlokalizowana, to wersja beta jest tylko dostępna dla użytkowników serwisu korzystających z amerykańskiej wersji językowej.

Firma zamierza upublicznić wyszukiwarkę w ciągu tygodni/miesięcy. W przyszłości ma się pojawić wsparcie dla aplikacji mobilnych, obsługa wszystkich języków, przeszukiwanie statusów i Open Graph.

Open Graph, czyli połączenie Graph Search z wyszukiwaniem lajków na stronach zewnętrznych. Zaprezentowano go już 3 lata temu:

Open Graph umożliwia indeksowanie stron internetowych pod względem ich „popularności” wśród użytkowników.

Tym samym firma przypomniała niejako, że jej starania o zbudowanie własnej, specyficznej wyszukiwarki trwają już od kilku lat. Zapewne to właśnie Graph Search miał na myśli Zuckerberg we wrześniu zeszłego roku.

Socjogram może okazać się jedną z najważniejszych funkcji Facebooka. Owszem, ktoś powie, że wyszukiwarka technologicznie wcale nie jest bardziej zaawansowana od rozwiązań konkurencji, szczególnie Google’a. Warto jednak pamiętać, że sam algorytm jest tylko jednym elementem całej układanki. Elementem najmniej ważnym, z punktu widzenia użytkownika. Użytkownik bowiem szuka określonych treści, jeśli więc baza danych jest uboga o nie, to nawet najlepszy algorytm nie zatuszuje tego faktu.

Źródła:

http://en.wikipedia.org/wiki/Facebook_Graph_Search

http://www.dobreprogramy.pl/

https://www.facebook.com/about/graphsearch

http://www.gazeta.pl/

http://actualfacebookgraphsearches.tumblr.com/

http://www.komputerswiat.pl

http://www.insidefacebook.com/

 Kamil Pludra, 94470

Semantyka stron WWW, czyli co nowego w HTML5?

Od dosyć dawna możemy projektować strony według standardu HTML5, jednakże nie wszystkie przeglądarki wspierają ten standard w równym stopniu. Także przed użyciem którejś z właściwości HTML5 warto sprawdzić, jakie przeglądarki obsługują daną opcję i na jakim poziomie.

Wracając do sedna, czyli do standardu HTML5, daje on wiele nowych możliwości, między innymi wprowadza elementy semantyczne, które nadają znaczenie sekcjom kodu dokumentu HTML, a użyte we właściwy sposób, mogą usprawnić działanie przeglądarek, wyszukiwarek i czytników ekranów dla osób niedowidzących i właśnie tymi elementami będę zajmował się w dalszej części artykułu.

Większość stron internetowych przed standardem HTML5 opierała się na elementach <div>, które nic nie mówią o zawartości znajdującej się wewnątrz elementu. Elementy te są proste w użyciu, a sposób wyświetlania i funkcję jaką pełnią możemy definiować arkuszami styli. Przyglądając się bardziej złożonemu dokumentowi HTML i elementom <div> trudno stwierdzić jaką funkcję one pełnią, tym bardziej, jeżeli nie ma żadnych komentarzy twórcy dokumentu, a klasy czy identyfikatory styli są nazwane w sposób nic nie mówiący człowiekowi. Dlatego aby odpowiedzieć sobie na to pytanie, jaką funkcję dany element <div> spełnia, należy zagłębić się w arkuszach styli, sprawdzając, jakie style są przypisane do danego elementu. Ale czy wiedza gdzie dany element jest umiejscowiony i w jaki sposób jest wyświetlany na stronie definiuję to jaką rolę pełni? Czy <div> umieszczony w dolnej części strony zawsze jest stopką? Albo czy menu zawsze znajduje się po lewej stronie strony? Dlatego HTML5 wprowadza nowe elementy semantyczne, które jednoznacznie mówią jaki element jaką pełni funkcję na stronie i zastępują zbyt ogólne elementy <div>, dzięki temu kod dokumentu jest łatwiejszy do edytowania i utrzymania, i to jest jeden z kilku powodów, aby używać nowe znaczniki. Drugim z powodów jest dostępność.  Strony dostępne to strony po których można nawigować za pomocą czynników ekranów, których używają osoby niedowidzące, dzięki elementom semantycznym łatwiej przychodzi znalezienie interesujących elementów strony. Kolejnym powodem jest optymalizacja pod kątem wyszukiwarek. Roboty przeszukujące sieć biorą pod uwagę elementy semantyczne dokumentu HTML, odpowiednie ich użycie może pomóc Twojej stronie znaleźć się na początku listy wyników wyszukiwania.

Nowe elementy semantyczne wprowadzają nową jakość w strukturze dokumentu, dzięki nim można oddzielić najpopularniejsze sekcje dokumentu a ponadto nadać znaczenie treściom w nich zawartych. Poza tym, nowe znaczniki nic nie zmieniają, nie są nim przypisane żadne style.

Jednym z najbardziej wyspecjalizowanych znaczników jest element <time>, w którym powinna być właściwie sformatowana  godzina bądź data na przykład <time>2013-11-24</time>.

Kolejnym elementem opisującym strukturę dokumentu jest element <header>,  w którym zawieramy nagłówek strony, czy też rozbudowany nagłówek artykułu. Pewnie teraz zastanawiasz się, co w wypadku, gdy na stronie będą występować oba nagłówki. Standard HTML5 nie zabrania kilkukrotnego użycia tego samego elementu semantycznego w obrębie jednej strony, jednakże im jest ich mniej i są bardziej przemyślane i właściwie użyte tym lepiej, ponieważ zbyt pochopne używanie nowych znaczników spowoduje powrót do tej samej sytuacji jak w wypadku ogólnych elementów <div>.

Następnym jest element <footer>, w której zawieramy stopkę dokumentu HTML.  Oczywiście każdy z tych elementów może zawierać inne elementy, także <div>.  Możemy na przykład umieścić informacje o autorze, menu nawigacyjne z poznanym już znacznikiem <nav>. Oczywiście wszystkich elementów nie powinnyśmy zawierać w elemencie <footer>, mogą być zawarte przed lub po tym znaczniku, ale w obrębie tego samego znacznika <div>, w którym jest zawarty element <footer>.

Niestety w HTML5 nie wprowadzono elementu <content>, w którym byłaby zawarta główna treść strony. Za to istnieje element <article> reprezentujący pewien oddzielny fragment treści, może to być wpis blogowy, czy to jakaś wiadomość. Oczywiście, w znaczniku <article> możemy zawrzeć poprzednie elementy takie jak <header> i  <footer>, w ten sposób otrzymamy artykuł z nagłówkiem, w którym będzie tytuł,  a może także podtytuł, notka o autorze.  Następnie zawieramy treść artykułu, w elemencie <div> lub <spam> a na koniec poznany także prędzej element <footer> w którym mogą być zawarte tak zwane copyrighty, czy odnośniki do innych stron. Tylko co w przypadku kiedy artykuł jest podzielony na kilka podstron? W takim przypadku, lepszym rozwiązaniem będzie, gdy każdy z części artykułu umieścimy w oddzielnym elemencie <article>.

Wyżej wspomniałem o artykule, w którego nagłówku występował także nagłówek, HTML5 wyróżnia element <hgroup>,  w którym możemy zawrzeć tytuł w elemencie <h1> a podtytuł w elemencie <h2>, jeżeli chcemy zawrzeć coś więcej, to lepiej zrobić to poza znacznikiem <hgroup>.

Mamy już zdefiniowany cały tekstowy artykuł, ale co jeśli wewnątrz tekstu będziemy chcieli zawrzeć jakiś obraz? Analogicznie jak w książkach, każdy z obrazów powinien być jednoznacznie związany z tekstem, dlatego będziemy go zawierać w elemencie <figure>. Dobrym pomysłem, jest także opis każdego z obrazu, taki opis powinien być umieszczany wewnątrz elementu <figcaption> i może on zastąpić atrybut alt ze znacznika <img>.

HTML5 wyróżnia także element <aside>, można w nim zawierać treść, który w jakiś sposób odnosi się do zawartości znacznika <article>. Może to być rozszerzenie jakiegoś zagadnienia, cytat, czy odnośnik zewnętrzny.

Elementy nawigacyjne powinniśmy zawierać w nowym elemencie <nav>, dlatego w tym znaczniku będziemy umieszczać odnośniki w obrębie danej strony lub do innych zewnętrznych stron.

Kolejnym nowym znacznikiem będzie element <section>, w którym zostają zwarte treści, nie pasujące do pozostałych elementów semantycznych.  Można w nim umieścić skróconą informację o nas, czy zestaw informacji kontaktowych, a także zbór treści na przykład lista newsów, czy też samoistne treści, które nie można nazwać artykułem. Może to być na przykład lista produktów na stronie sklepu.

Podsumowując, HTML5 wprowadza kilka nowych elementów semantycznych, przy pomocy których można zbudować strukturę semantyczną dokumentu, która niesie za sobą jednoznaczne informacje semantyczne, nie tylko dla autorów, ale także użytkowników przeglądających strony przy pomocy czytników ekranów dla osób niedowidzących a także dla robotów wyszukiwarek indeksujących stron, które biorą pod uwagę zwartość elementów semantycznych, gdzie zysk jest obopólny, użytkownicy wyszukiwarek otrzymują lepiej dopasowane wyniki a twórcy stron wyższą pozycję w wynikach wyszukiwania.

Oczywiście, zasób znaczników jest dość ubogi, z jednej strony to wada, ponieważ nie do końca możemy dopasować semantykę do prezentowanej zawartości na stronie, a z drugiej zaleta, ponieważ twórcy stron internetowych nie muszą uczyć się mnóstwa nowych znaczników, które pewnie i tak nie oddadzą całej semantyki jaką można spotkać na stronie internetowej. Reasumując, elementy semantyczne to pierwszy krok, do stworzenia w pełni semantycznych sieci WWW.

Piotr Michalak