Archive for ‘Social network’

Grudzień 1, 2014

Esy floresy i fantasmagorie sieciowo społecznościowe

- autor: tsissput

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:

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:

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

Grudzień 8, 2013

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

- autor: tsissput

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.

Tabela 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.

Tabela 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:
http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
http://www.cs.rpi.edu/~zaki/PaperDir/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

Listopad 24, 2013

Graph Search, czyli semantyczna wyszukiwarka Facebooka.

- autor: tsissput

graph-search_320x197Graph 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

Listopad 10, 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

Luty 21, 2013

SignedNetworkGenerator

- autor: tsissput
  • Przemysław Wróblewski 89846
  • Marcin Wojdowski 89843

Program ma za zadanie generowanie sieci z wiązaniami ujemnymi i dodatnimi.

Program realizuje następujący scenariusz:

  1. Załadowanie danych konfiguracyjnych
  2. Pobranie z fabryki NetworkFactory2 głównego algorytmu przetwarzania, impl w pakiecie org.tsiss.sng.network.creators
  3. W zależności od głównego algorytmu przetwarzania klass wspierajacych przetwarzanie. Przykładowe wartości z pliku ApplicationContext:
    1.  ac.getProbability(); – zwraca model prawdopodobienstwa dla procesu tworzenia krawedzi wewnątrz grupy i na zewnątrz(osobne).
    2. ac.getGroupChooser(); – zwraca model wyboru grupy do przydziałów nowych elementów.
    3. ac.getExtNegativeEdge(); – zwraca model wyboru docelowego wierzchołka dla negatywnej zewnętrznej krawedzi
    4. ac.getExtPositiveEdge();- zwraca model wyboru docelowej grupy dla negatywnej zewnętrznej krawedzi
    5. ac.getNodeChooser();- zwraca model wyboru docelowego wierzchołka dla wybranej grupy
    6. ac.getAgeFunction();- zwraca funkcje postarzająca krawędzie.

Głównym plikiem konfiguracyjnym projektu jest plik sng.properties.

W środku znajdziemy następujące przykładowe parametry:

  • nodes=40 ­– ilośc węzłów
  • iterations=40000 – ilośc iteracji algorytmu
  • edges=220 – max ilość krawędzi
  • negative-edge=1 – możliwość tworzenia negatywnych krawedzi
  • bidirected=true – czy sieć jest skierowana
  • minimum-edge-weight=-5.0
  • maximum-edge-weight=5.0
  • output-file=d:\\sng\\sng.gdf – plik wyjsciowy
  • output-type=GDFFile – format wyjsciowy
  • groups=5 – ilość dostępnych grup
  • AgeFunction=LinearFunction – nazwa klasy użytej jako funkcja postarzania(pakiet: org.tsiss.sng.edge.age)
  • probability  = ParametrizedProbability – nazwa klasy użytej jako funkcji określającej możliwość powstania krawędzi (pakiet: org.tsiss.sng.probability.create.edge)
  1. — parametry specyficzne dla danej klasy
  2. ParametrizedProbability.createInternalEdgeProb=0.8
  3. ParametrizedProbability.createExternalEdgeProb=0.6
  4. ParametrizedProbability.isNegativeEdgeProb=0.5
  •  groupChooser=PopularPreference – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowego obiektu (pakiet: org.tsiss.sng.probability.choose.group)
  •  nodeChooser  = NodeDegreePreference – nazwa klasy użytej jako funkcji wybierającej wierzchołek z podanego zbioru, np. Wybranej grupy (pakiet: org.tsiss.sng.probability.choose.node)
  1.  — parametry specyficzne dla danej klasy
  2. NodeDegreePreference.handicap = 2
  3. NodeDegreePreference.degreeWeight =1.5
  • externalNegativeEdge = GroupNegativePreferenceWithPositiveInfluence – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowej negatywnej krawedzi (pakiet: org.tsiss.sng.probability.choose.group)
  1. — parametry specyficzne dla danej klasy
  2. GroupNegativePreference.handicap = 1
  • externalPositiveEdge = GroupPositivePreference – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowej pozytywnej krawedzi (pakiet: org.tsiss.sng.probability.choose.group)
  1. — parametry specyficzne dla danej klasy
  2. GroupPositivePreference.handicap = 2

Jak widzimy po skompilowaniu projektu możemy zmieniać mechanizm działania aplikacji bez potrzeby ponownej przebudowy projektu.
Możliwości aplikacji możemy rozszerzać dodając nowe implementacje klas.
Należy jednak pamiętać,że wszystkie klasy utworzone w pakiecie org.tsiss.sng.probability.* i org.tsiss.sng.edge.age należy zarejestrować w odpowiedniej enumeracji w pakiecie org.tsiss.sng.enum.

Sytuacja jest podobna z formatami wyjściowymi utworzonej sieci (pakiet: org.tsiss.sng.outputs).
Niestety format UCINet wymaga poprawek.

Specyficzne parametry dla danych klas:

Jeżeli zaszłaby potrzeba pobrania z pliku konf. Specyficznego nowego parametru, zapisujemy go wg. schematu:

„NazwaKlasy.nazwaParametru=Wartość”

Po dodaniu parametru należy go zarejestrować w enumeracji org.tsiss.sng.enum.ApplicationOption.java, np:

AGE_FUNCTION(„ageFun”, „AgeFunction”,true,”Name algorithm used to determine age function”,”NoFunction”),

PARAM_NAME(„shortName”, „LongName”,true,”Description”,”DefaultValue”),

Jeżeli mamy już zarejstrowany parameter w klasie ApplicationContext dodajemy:

  1. pole przechowujace wartość naszego paramteru
  2. w metodzie setApplicationValue, dodajemy warunek case i metode konwersji naszego paramteru z klasy String
  3. utworzenie gettera dla pola z pkt 1.

To wszystko.

Jeżeli z jakiś względów użytkownik, nie może zarejestrować, dodać wpisu, może wykorzystać metode ApplicationContext.getProperty(String key, String defaultValue), by pobrać wartośc parametru prosto z pliku sng.properties. Jednak należy pamiętać, że powyższe rozwiązanie nie jest zalecane.

Źródła projektu dostępne pod adresem: http://sirius.cs.put.poznan.pl/~inf89843/tpd2/tsiss/sng.zip

Przykładowo wygenerowane sieci: http://sirius.cs.put.poznan.pl/~inf89843/tpd2/tsiss/sng_net.rar

Uruchamanie:

“java –jar SignedNetworkGenerator.jar plik_konf.properties”

Jako jedyny parametr funkcja przyjmuje relatywną ścieżkę do pliku konfiguracyjnego. Jeżeli użytkownik pominie parametr, aplikacja spróbuje załadować plik sng.properties z katalogu aplikacji.

Miłego korzystania:)

Luty 20, 2013

System Rekomendacji Gier Planszowych

- autor: tsissput

Cel projektu:

Celem projektu było stworzenie systemu będącego w stanie polecać gry planszowe na podstawie wybranej gry planszowej lub preferencji mechanik sterujących grami planszowymi.

Realizacja projektu:

W celu ustalenia jakie gry można polecić, w zależności od wybranego przez użytkownika tytułu, należało stworzyć graf podobieństw pomiędzy grami planszowymi. Do ustalenia podobieństwa pomiędzy nimi zostały wykorzystane ich mechaniki. Wyróżnia się ponad 40 różnych mechanik sterujących grami planszowymi, każda gra wykorzystuje dowolną liczbę tych mechanik w swoim działaniu. Fakt ten został wykorzystany do ustalania podobieństwa między poszczególnymi tytułami- dla każdej pary gier planszowych sprawdzana jest liczba mechanik, z których oba tytuły korzystają oraz liczba różnych mechanik, które te gry wykorzystują. Iloraz tych dwóch wartości daje nam miarę podobieństwa jednej gry planszowej do drugiej. Wartości tej miary stanowią krawędzie w grafie podobieństw pomiędzy grami planszowymi. Ponieważ miara ta jest wartością symetryczną, krawędzie w grafie są nieskierowane. Aby zniwelować dużą ilość krawędzi, szczególnie wychodzących od wierzchołków reprezentujących gry z dużą ilością wykorzystanych mechanik, zastosowano próg odcięcia na poziomie 0,3. Gdy użytkownik szuka gry podobnej do wymienionego tytułu, system zwraca wszystkie wierzchołki, które posiadają krawędź prowadzącą do wierzchołka reprezentującego wybraną grę. Wszystkie tytuły są wyświetlane wg miary podobieństwa w kolejności malejącej wraz z najważniejszymi informacjami o danych tytułach. System udostępnia także alternatywną metodę rekomendacji gier. Pozwala on na wybranie kilku mechanik gier planszowych, po czym dodawany jest tymczasowy wierzchołek grafu i tworzone są krawędzie wychodzące z niego zgodnie z zasadami wymienionymi powyżej. Następnie zwracane są wszystkie tytuły które zostały połączone krawędzią z tymczasowym wierzchołkiem. Po dokonaniu rekomendacji tymczasowy wierzchołek zostaje usunięty z grafu.

Wykorzystane technologie:

– Java
– Play Framework
– Twitter bootstrap

Wizualizacja sieci oraz działania systemu:

Graf podobieństw gier planszowychstronaGłówna wynikigry

Kody źródłowe:

http://sirius.cs.put.poznan.pl/~inf89752/iswd/tsiss.zip

 

Autorzy:

Jakub Jaróżek
Dawid Neumann

Luty 19, 2013

Semantic WoW

- autor: tsissput

Cel projektu

Celem projektu było stworzenie i wizualizacja grafu powiązań pomiędzy graczami World of Warcraft – jednej z najpopularniejszych gier MMORPG w sieci. Niezbędne dane pobrano korzystając z WoW API do bazy danych, przetworzono i uzyskano graf w formacie Netdraw VNA. Wizualizacji dokonano z użyciem programu Gephi.

Zastosowane technologie

Informacje z WoW API pobrano z użyciem aplikacji konsolowej napisanej w języku Java. Dane przechowywano w bazie MongoDB, zaś przetwarzanie odbywało się przy pomocy wspomnianej aplikacji oraz skryptów JavaScript. Dalszych operacji na grafie oraz wizualizacji dokonano w programie Gephi.

Zaimplementowana aplikacja

Jak wspomniano aplikacja jest konsolowa, umożliwia następujące operacje:

  • wczytanie pliku z nazwami gildii,
  • pobieranie nie ściągniętych gildii (na podstawie wczytanej listy nazw),
  • pobieranie nie ściągniętych postaci (na podstawie listy nazw członków gildii),
  • oba powyższe,
  • usunięcie zawartości bazy danych,
  • wygenerowanie pliku z grafem na podstawie pobranych danych przetworzonych za pomocą skryptów JS.

cmd

Architektura aplikacji

Ze względu na sposób udostępniania danych przez WoW Api, aplikacja wymaga nazw gildii, których ma dotyczyć analiza (względnie nazw wszystkich gildii na serwerze). Informację tę uzyzkano z serwisu WoW Progress i wczytywano z plików.
arch

Model ORM

Do mapowania obiektowo relacyjnego wykrorzystano bibliotekę Morphia współpracującą ze biblioteką Java sterowników bazy MongoDB.
orm

Uzyskane dane

Pobrano informację o graczach serwera Arathor-EU należących do gildii uzyskanych z WoW Progress. Dane pobierano na przestrzeni 5 dni w pierwszej połowie stycznia 2013. Po zapisie do bazy danych jej rozmiar wynosił ponad 35GB.

Pobrano informacje o 302 gildiach oraz 38 629 postaciach. Ze względu na rozmiary danych i przyjęty sposób analizy połączeń zdecydowano się przetworzyć jedynie postaci z 5 najlepszych (pod względem liczby punktów osiągnięć):

  • Alliance of Destiny
  • Maligned
  • Velvet Glove
  • Retired
  • Blacksail Pirates

Do tych gildii należy 1760 postaci powiązanych łącznie z 650 kontami graczy.

Graf uzyskany na podstawie top 5 gildii

Postaci są opisane takimi atrybutami jak: średni poziom przedmiotów, klasa, rasa, płeć, poziom postaci, oraz informacją czy jest to główna postać gracza. Wiele postaci gracza udało się identyfikować na podstawie identycznej listy osiągnięć zdobywanych w tym samym momencie. Za główną uznawano tę o najwyższym poziomie w danej gildii (tak więc gracz mógł mieć więcej niż jedną główną postać). Krawędź przechowuje również informację o tym, czy łączy dwie główne postaci, oraz o minimalnej rozbieżności czasowej w zdobyciu osiągnięcia przez obie postaci.

Jako że WoW API nie udostępnia bezpośrednio informacji o tym jak gracze dobierają się w drużyny, dwie postaci połączono krawędzie jeżeli zdobyli osiągnięcie w podobnym czasie (założono, że zdobywali go wspólnie), lub są w tej samej drużynie pvp. Wagą krawędzi ustanowiono liczbę osiągnięć, które zostały zdobyte w podobnym (w odstępie pięciu minut) czasie.

W rezultacie otrzymano:

  • 48792 Krawędzi
  • 36859 krawędzi między głównymi postaciami
  • 153 krawędzie pvp

W pierwszym pliku  krawędzie poprowadzono jedynie pomiędzy głównymi postaciami, oraz pomiędzy wszystkimi postaciami danego gracza. W drugim  umieszczono wszystkie krawędzie.

Wizualizacja

Poniższe rysunki przedstawiają grafy, w którym krawędzie poprowadzono jedynie między głównymi postaciami. Pierwsze dwie ilustrują wspólne zdobywanie osiągnięć, podczas gdy w trzecim zawarto informacje o grze arenowej. Na dwóch początkowych obrazkach pozostawiono jedynie krawędzie między postaciami, które przynajmniej jedno osiągnięcie zdobyły w tym samym momencie, i to tylko te, których waga przekraczała 40. Wielkość wierzchołka odpowiada jego wartości pagerank, zaś kolor wskazuje przynależność do gildii (na pierwszym), poziom posiadanego ekwipunku (na drugim).

guilds_circle_2guilds_circlepvp

Styczeń 28, 2013

RideTogether

- autor: tsissput

Idea aplikacji

RideTogether to aplikacja internetowa ułatwiająca wspólne podróżowanie. Dzięki niej osoby podróżujące w tą samą stronę mogą pojechać jednym samochodem i trochę zaoszczędzić. Użytkownik ma do dyspozycji intuicyjne GUI które udostępnia kilka podstawowych czynności:

  • stworzenie konta i logowanie;
  • dodanie nowej trasy;
  • dołączenie do istniejącej trasy;
  • wyświetlenie szczegółów istniejącej trasy – w tym miejscu użytkownikowi prezentowana jest mapa z zaznaczonym przebiegiem trasy, a także orientacyjną odległością i czasem przejazdu;
  • udostępnienie na Facebooku informacji o planowanej podróży.

ridetogether

Screen z aplikacji prezentujący jej funkcjonalność.

Zastosowane technologie

Projekt został napisany w całości w języku JavaScript. Wykorzystuje innowacyjne technologie – serwer JavaScript’owy Node.js oraz MongoDB – nierelacyjny system zarządzania bazą danych.

Oprócz tego wykorzystywane są:

  • Google Maps JavaScript API v3 – do prezentacji przebiegu trasy z pomocą map Google;
  • Facebook JavaScript SDK – wykorzystane do dodania na stronie przycisku Share, pozwalającego na umieszczenie na tablicy użytkownika informacji o przejeździe, wraz z odnośnikiem do strony;
  • Twitter Bootstrap – darmowa kolekcja narzędzi do tworzenia aplikacji internetowych, zawierająca gotowe szablony HTML i CSS.

Możliwości rozwoju

W przypadku dalszego rozwoju pod uwagę brane są:

  • bardziej rozbudowana integracja z Facebook (logowanie, komentowanie);
  • możliwość wybierania, kto z nami będzie jechał;
  • ocenianie podróżników;
  • modyfikowanie trasy, dodawanie punktów kontrolnych, możliwość dołączania i odłączania się w dowolnym miejscu;
  • wykorzystanie innych środków transportu niż samochód.

Autorzy projektu:

Kamil Ciecierski, Szymon Kaliski, Maciej Matuszewski

Grudzień 3, 2012

„Why the Semantic Web will never work”

- autor: tsissput

Zebranie i analiza informacji przedstawionych na wykładzie Jim’a Hendler’a
pt.: „Why the Semantic Web will never work”

Jim Hendler

Ideą organizowanej od 2011 konferencji Extended Semantic Web Conference (ESWC) jest zebranie osób zaangażowanych w różne aspekty technologii semantycznych, a także innych obszarów Informatyki, które wiążą się z pojęciem Semantic Web. Ma ona na celu sprowokowanie wymiany informacji pomiędzy różnymi społecznościami wewnątrz i spoza dziedzin Informatyki i Telekomunikacji.

Konferencja ta powstała jako rozwinięcie European Semantic Web Conference. Wykład wprowadzający, tzw. keynote,  prowadził profesor Jim Hendler, znany ze swojego znaczącego wkładu w zakresie Semantic Web, a także całej dziedziny Informatyki oraz Kognitywistyki. Zapowiadający nazywa go nawet Papieżem Semantic Web. Aktualnie pełni stanowisko Tetherless World Senior Constellation Professor na wydziałach Department of Computer Science oraz Cognitive Science Department  Rensselaer Polytechnic Institute (RPI), w Troy w Nowym Yorku.

Tytuł wykładu ma prowokacyjne brzmienie i został celowo umieszczony w cudzysłowie, ze względu na dwuznaczność. Jim Hendler dokonuje przeglądu aktualnych sukcesów technologii semantycznych względem wczesnej wizji Semantic Web oraz identyfikuje problemy dotyczące aktualnych rozwiązań oraz najnowszych próbach ich rozwiązania. Pokazuje więc aktualne dokonania z dwóch perspektyw:

wyjaśnienie tytułu

Początkowa wizja

W 1994 roku  na konwencji WWW Tim Berners-Lee dokonał prezentacji, w której pokazał swoją wizję sieci web. Część tego czym sieć jest określił w następujący sposób: „Dokumenty w sieci web opisują prawdziwe obiekty i wyimaginowane pojęcia oraz nadają szczególne związki pomiędzy nimi”. Tim Berners-Lee wymyślił więc to, co dzisiaj nazywamy Semantic Web, a hyperlinki nie miały być zwykłymi wskaźnikami na inne strony internetowe, lecz miały reprezentować relacje pomiędzy stronami.

Innm pomysłem, zaprezentowanym w 1999 roku przez Jim’a Hendler’a, był Agent markup language, który polegał na zbudowaniu semantycznego języka, który wiązałby informacje na stronie internetowej z semantyką (ontologią) odczytywalną maszynowo. Obecnie pomysł ten rozwijany jest w ramach projektów OWL, SHOE, I3 lub ARPI.

Co wiąże oba te pomysły, to koncepcja, by pewne elementy na stronach web opisywały jakie treści one zawierają i co one znaczą.

schemat współdziałania ontologii sieciowych

schemat współdziałania ontologii sieciowych

Wyobrażano sobie również, że ontologie webowe, czy też semantyka umieszczona na stronach web będzie miała charakter zgoła inny od tradycyjnych systemów reprezentacji wiedzy (KR). Różne dokumenty sieci web, mogły by być opisywane przez różne słowniki, które były by wobec siebie w różnym stopniu mapowalne. Częściowa mapowalność i niespójność tychże ontologii powodowała by więc błędy takie błędy jakie można spotkać przeglądając strony internetowe, np. 409, lecz taki schemat umożliwiałby dużą skalowalność, elastyczność, a w rezultacie dużą ilość użytkowników i duży wpływ na sieć web.

Do innych wczesnych koncepcji dotyczących Semantich Web należały:

  • przeszukiwanie sieci w poszukiwaniu konkretnej odpowiedzi, nie w poszukiwaniu dokumentu, który wydaje się adekwatny
  • użycie istniejących ontologii w ramach
  • use x ontology on webpages
  • aspekt usługi
  • active notion – a way of exchanging information “This term came from here” linking

Zwycięstwo Semantic Web

Gdy Semantic Web dopiero się rozwijało, myśl o tym, że rząd wielkości o jakim należy myśleć w przypadku technologii semantycznych to przynajmniej miliony, wzbudzała śmiech.  Aktualnie liczba stron internetowych, które zawierają informację semantyczną i liczba trójek semantycznych – triple (URI obiektu, URI obiektu, URI związku), które są generowane oraz zbiorów danych które są dostępne przekroczyła nawet najśmielsze oczekiwania.

Aktualnie wiele z dużych firm zajmuje się technologiami semantycznymi. Są one pozytywną siłą dla rozwoju pewnych obszarów Semantic Web, przykładowo semantycznego wyszukiwania (np. Google Knowledge Graph) o którym szerzej mówi Peter Mika w swojej prezentacji Making the Web searchable, a także dla promocji, reklamy i marketingu. W szczególności, bardzo prężnie rozwijają się nowe firmy, które służą jako pośrednicy pomiędzy jednostkami dostarczającymi usługi lub produkty (w szczególności treści), a konsumentami. Pośrednictwo to polega na budowaniu informacji preferencyjnej użytkowników na podstawie danych semantycznych i kierowaniu do nich odpowiednich ofert.

Innym dużym czynnikiem wpływającym na postęp Semantic Web są implementacje idei o nazwi Open Data, przykładowo  Facebook Open Graph lub Open Goverment Data. W przypadku Facebook Open Graph, jedną z możliwości umieszczenia przycisku „Lubię to” na stronie internetowej jest użycie RDF’a, który generuje trójki danych semantycznych. W Październiku 2010 Facebook zarejestrował około 3 miliony „Lubię to” dziennie pochodzące z tego źródła, gdzie pojedyńcze kliknięcie może generować więcej niż 1 trójkę semantyczną (triple). Estymowano wtedy, że jedynie około 10%-15% przycisków „Lubię to” na stronach było umieszczone w postaci RDF’a, a Facebook bardzo silnie stara się, by zachęcić jak największą ilość osób do zmiany na ten typ przycisków. Okazuje się, że przyciski Facebook’a same generują więcej trójek z informacją semantyczną niż  kiedykolwiek przewidywano dla całej sieci, a zyski z reklamy przeprowadzanej na podstawie tej informacji są głównym źródłem dochodów Facebook’a, a także innych firm – np. Zynga, która zarabia więcej pieniędzy niż jakakolwiek inna firma wytwarzająca gry komputerowe, ponieważ jako pierwsza znalazła sposób na wykorzystanie tej informacji.

Krytyka Semantic Web

Pomimo zaangażowania ze strony dużych graczy na rynku wyszukiwarek internetowych, aktualnie nadal wyszukiwanie wykonywane jest w tradycyjny sposób, po słowach kluczowych, w celu znalezienia dokumentów, które wydają się adekwatne i mogą zawierać wyszukiwaną odpowiedź.

Początkowo wydawało się, że folksonomia okaże się najlepsza do umieszczania informacji semantycznej, jednak w dużej mierze technologie związane z tagowaniem zawiodły poza zastosowaniami w sieciach społecznościowych. Podstawowym problemem, dla tagowania był brak kontekstu, a więc zatracenie znaczenia wśród wielu innych obiektów otagowanych w ten sam sposób. W przypadku sieci społecznościowej tag, przykładowo imię i nazwisko, będzie miał konkretne znaczenie ponieważ będzie on na stronie osoby, która mówi o osobie ze swojej listy znajomych.

most used

Zarzuty dotyczące braku skalowalności, elastyczności i stabilności Semantic Web okazały się nieuzasadnione, co potwierdzają wcześniejsze przykłady. Co więcej, liczba ogólnie dostępnych URI, które mają swoją semantykę, przykładowo z Open Goverment Data rośnie bardzo szybko.

Pewnym problemem aktualnego rozwoju Semantic Web, jest to, że większość zastosowań korzysta głównie z technologii semantycznych „niższego poziomu”, podczas gdy wiele z ciekawych, użytecznych, a co więcej ustandaryzowanych z nich nie jest znana lub nie jest używana przez większość osób.

Konkluzja

Dlaczego Semantic Web miało by nigdy nie działać? Jim Hendler odpowiada, że nie ma żadnego powodu, aby tak było – Semantic Web istnieje, działa i będzie działać. Nie jest to jednak Semantic Web, z pierwotnej wizji. Konieczny jest powrót i uaktulanienie do pierwotnych pomysłów i unifikacja aktualnie konkurujących ze sobą modeli powiązanych danych (linked-data) i odczytywalnych maszynowo słowników. W szczególności problemem, który musi zostać rozwiązany jest integracja ontologii i rozój mechanizmów pracy z danymi, które mogą zawierać poważne, nierozwiązywalne sprzeczności.

Wg mojej oceny sukces Semantic Web jest potwierdzony przez, to z jakim zaangażowaniem zajmują się technologiami semantycznymi duże firmy takie jak Facebook, Google, Oracle, Amazon, czy też Microsoft, a w szczególności w jaki sposób użytkownicy zarówno generują i konsumują informację semantyczną, poprzez korzystanie z aplikacji społecznościowych, aplikacji mobilnych i webowych (w tym np. gier na Facebook’u). Innym aspektem, który w dużym stopniu napędzia rozwój Semantic Web jest sposób w jaki niektóre z firm zaangażowane w tworzenie i gromadzenie informacji semantycznej współpracują z innymi firmami – przykładowo umieszczanie przycisków „Lubię to” na stronie udostępnia informacje, zarówno dla Facebook’a, jak i dla właściciela strony internetowej. Innym przykładem jest sposób w jaki Facebook i Google umożliwiają deweloperom publikowanie aplikacji, które potencjalnie mogą być agentami przetwarzającymi lub generującymi informację semantyczną.

Autor: Michał Turek

Źródła: opisywany wykład, strona Jim’a Hendler’a, artykuł o Google Knowledge Graph, strona konferencji ESWC , artykuł wiki o Clay’u Shirky, artykuł wiki o KR, artykuł o Open Data, Facebook Open Graph, Open Government Data.

 

Grudzień 3, 2012

Wolfram Mathematica 9: co nowego?

- autor: tsissput

Nowa wersja Wolfram Mathematica 9

W ostatnich dniach miała miejsce premiera nowej wersji znanego oprogramowania obliczeniowego firmy Wolfram – Mathematica 9®. Jak informuje  producent, w wersji dziewiątej możemy znaleźć garść interesujących nowinek. Wśród nich z punktu widzenia naszego przedmiotu bardzo ciekawe wydaje się dodanie wsparcia dla analizy sieci społecznościowych.

Nowości

Wśród nowości producent wymienia na swojej stronie internetowej m.in.

  • Rozbudowane podpowiedzi do wprowadzanych komend jak i sugestie dalszych kroków po otrzymaniu wyniku
  • Wspomniane już wsparcie dla analizy sieci społecznościowych
  • Wbudowane jednostki miar
  • Rozwinięta możliwość tworzenia losowych zbiorów danych o podanym rozkładzie
  • Integracja z językiem R
  • Ulepszone przetwarzanie obrazów, dodanie m.in. wyszukiwanie twarzy, przetwarzanie obrazów 3D
  • Przetwarzanie sygnałów

Pełna lista zmian jest znacznie większa. Pełna lista zmian znajduje się pod adresem [1]

Analiza sieci społecznościowych

W dalszej części wpisu skupimy się na możliwościach programu Mathematica w kwestii analizy sieci społecznościowych.

Dostępne możliwości

Program Mathematica umożliwia import danych z bardzo szerokiej gamy formatów. Jednocześnie dla sieci społecznościowych istotne jest pobieranie danych „żywcem” z serwisu funkcjonującego w Internecie. Od wersji dziewiątej otrzymujemy taką możliwość w przypadku chociażby najbardziej popularnych portali społecznościowych, jakimi niewątpliwie są Facebook i Twitter.

Przy wizualizacji danych otrzymujemy możliwość wyszukiwania różnorakich wspólnot, czy też punktów centralnych w grafach. Oznaczanie klik, obliczanie homofilii i podobieństwa również nie powinno sprawiać problemów. Istnieje możliwość wszelakiego ograniczania danych w celu znalezienia przypadków spełniających określone kryteria.
math9_img1

Dostępne funkcjonalności

Poniżej przedstawiono wykres możliwości programu Mathematica oraz dostępność podobnych funkcjonalności w innych programach zajmujących się tą samą tematyką. Pod uwagę wzięto następujące oprogramowanie:

  • igraph 0.6
  • NetworkX 1.7
  • UCINET 6

Jak możemy odczytać z wykresu, istnieje cała gama funkcjonalności, które oferuje nam wyłącznie najnowsze wydanie pakietu Mathematica.

math9_img2

Wydajność

Chcąc sprawdzić wydajność oprogramowania, wykonano pomiar czasu wykonania następujących czynności:

  • Fast Simulation of Scale-Free Networks
  • Fast Community Detection in Networks
  • Fast Centrality and Prestige Computation

Pod względem wydajności Mathematica nie jest już tak czysto i klarownie lepsza od swojej konkurencji. W większości przypadków wypada ona jednak przynajmniej tak dobrze, lub minimalnie gorzej niż konkurencja.

Dla symulacji „Scale-Free Networks” czasy wykonania operacji przez NetworkX 1.7 są zazwyczaj nawet o ok. 200% gorsze. Program igraph 0.6 jest w tej kwestii znacznie lepszy i przegrywa z Mathematicą jedynie o ok. 30-40%.

math9_img3

„Community Detection” – tutaj trudno już mówić o jednoznacznej przewadze któregokolwiek z programów. Praktycznie tylko dla pojedynczego zbioru danych Mathematica ma sporą przewagę. Da większej ilości danych wyniki uzyskane przez igraph 0.6 są bardzo zbliżone. NetworkX 1.7 w mniejszym lub większym stopniu, ale zawsze przegrywa z konkurencją.
math9_img4

Ostatni test to „Fast Centrality and Prestige Computation”. Podobnie jak w pierwszym przypadku NetworkX 1.7 zostaje daleko w tyle. Wyniki Mathematica 9 oraz igraph 0.6 są bardzo zbliżone jednak zawsze minimalnie lepszym okazuje się pierwszy produkt.

math9_img5

Sprzęt na jakim wykonano obliczenia to Intel Core 2 Duo 3.06 GHz Mac OS X Lion.

Opinia autora artykułu

Mathematica 9 wydaje się bardzo solidnym rozwiązaniem. Wprowadzone w najnowszej wersji innowacje dają pole do popisu w kolejnych już dziedzinach. Mankamentem na pewno jest fakt, że oprogramowanie jest komercyjne. Moim zdaniem warto zapoznać się z omawianym oprogramowaniem podczas przedmiotu Technologie Semantyczne i Sieci Społecznościowe, aby potwierdzić, lub obalić dobre oceny wystawione przez samego producenta.

Ciekawostka

Na koniec ciekawostka odnośnie programu. Nazwę „Mathematica” zasugerował  Stephenowi Wolframowi współzałożyciel firmy Apple, Steve Jobs. Wcześniej Wolfram myślał o takiej nazwie, ale pomysł odrzucił.

Źródła

http://blog.wolfram.com/2012/11/28/mathematica-9-is-released-today/

http://www.wolfram.com/mathematica/new-in-9/social-network-analysis/

Linki

[1] http://www.wolfram.com/mathematica/new-in-9/

Autor: Marcin T.