Archive for Styczeń 2nd, 2012

Styczeń 2, 2012

Słów kilka o historii wyszukiwarek internetowych

- autor: tsissput

Na początku był Chaos. Z Chaosu wyłonili się pierwsi bogowie.” – tym oto cytatem można by opisać początki wyszukiwarek internetowych. Okres ich bujnego rozwoju przypadł na początek lat dziewięćdziesiątych ubiegłego stulecia.

Jako pierwszy z chaosu wyłonił się Archie. Jego nazwa pochodziła od angielskiego słowa archiev z pominięciem litery “v”. Było to pierwsze narzędzie do wyszukiwania treści w otchłaniach internetu. Jaka była zasada jego działania? Otóż Archie pobierał spis plików z serwerów FTP i łączył je w jeden ogólnie dostępny plik. Wyszukiwanie odbywało się poprzez wykorzystanie Unixowej komendy grep. Dostęp do zasobów Archie’go odbywał się początkowo przez Telnet lecz szybko został udostępniony również interfejs umożliwiający dostęp do zasobów przez WWW. Jego ogromną ułomnością było to, że zważywszy na ograniczone zasoby pamięci ówczesnych komputerów, nie indeksował on zawartości tekstowej stron.

Niedługo po powstaniu pierwszego narzędzia będącego protoplastą dzisiejszych wyszukiwarek internetowych w roku 1991 został wynaleziony zupełnie nowy, jak na tamte czasy, protokół internetowy o dźwięcznej nazwie Goopher. Umożliwiał on hierarchiczne indeksowanie plików tekstowych. Dla zainteresowanych polecam wtyczkę do przeglądarki Firefox (o nazwie OverbiteFF) umożliwiającą przeszukiwanie zasobów Gophera z wykorzystaniem przeglądarki internetowej, aby zobaczyć jak wyglądało wyszukiwanie informacji w internecie bez dzisiejszych dobrodziejstw technologicznych.

W oparciu o zasoby Gophera powstały dwie kolejne wyszukiwarki internetowe: Veronica i Jughead. Veronica czyli Very Easy Rodent-Oriented Net-wide Index to Computerized Archives umożliwiła wyszkukiwanie z użyciem słów kluczowych, natomiast Jughead (Jonzy’s Universal Gopher Hierarchy Excavation And Display) pozwalał uzyskiwać informacje z różnych serwerów Gophera.

W roku 1993 Oscar Nierstrasz z Uniwersytetu w Brnie korzystając z faktu istnienia wielu list stron internetowych postanowił pobrać ich zawartość, ujednolicić ich formę oraz udostępnić interfejs użytkownika pozwalający na łatwe przeszukiwanie zawartości. W ten oto sposób postał W3 Catalog zaimplementowany z wykorzystaniem języka skryptowego Perl.

W tym samym roku Mathew Grey z uniwersytetu MIT zaprojektował i wykonał prawdopodobnie pierwszego robota internetowego o nazwie World Wide Web Wanderer. Powstał on w celu zmierzenia rozmiaru sieci WWW lecz dzięki zebranym przez niego informacjom został utworzony indeks stron o nazwie Wandex. Robot przemierzał sieć co miesiąc, aż do czerwca roku 1995. Informacje przez niego zebrane posłużyły do przygotowania raportu, którego wyniki zamieszczam w poniższej tabeli. Pełna treść raportu jest dostępna pod adresem: http://www.mit.edu/people/mkgray/growth. Twórca Wandexa jest obecnie pracownikiem firmy Google.

Month # of Web sites % .com sites Hosts per Web server
06.1993 130 1.5 13,000
12.1993 623 4.6 3,475
06.1994 2,738 13.5 1,095
12.1994 10,022 18.3 451
06.1995 23,500 31.3 270
01.1996 100,000 50.0 94

Kolejną wartą uwagi przeglądarką był Aliweb, który ukazał się światu w listopadzie 1993 roku. W przeciwieństwie do Wandexa informacje, które się w nim znajdowały nie pochodziły dzięki robotowi internetowemu. Działanie Aliweb było bajecznie proste. Każda nowo postała strona musiała zostać do niego zgłoszona przez jej autora. Dodatkowo w głównym katalogu musiał znajdować się plik w określonym formacie informujący o tym, że strona ma zostać zaindeksowana.

Rok 1993 okazał się być bardzo płodny pod względem powstawania wyszukiwarek internetowych. W grudniu została wydana na świat wyszukiwarka JumpStation. Ten wynalazek był najbliższy temu z czym obecnie kojarzy nam się wyszukiwarka internetowa. Katalog stron był budowany z wykorzystaniem robota internetowego, a interfejs użytkownika został przygotowany z wykorzystaniem formularzy HTMLowych. Autorem JumpStation był Jonathon Fletcher, student University of Sterling. Projekt przestał być kontynuowany kiedy Fletcher opuścił uczelnię w roku 1994. Autor tego innowacyjnego jak na tamten czas pomysłu nie zdołał pozyskać środków finansowych na kontynacje swojego projektu. Kiedy projekt upadł, baza danych zawierała 275 tysięcy stron internetowych. JumpStation przy indeksowaniu stron wykorzystywał ich tytuł oraz meta tagi zawarte w nagłówu strony. Jego ogromną wadą był brak rankingu stron, co wpływało na niską jakość wyników wyszukiwania.

Niecałe pół roku później w kwietniu 1994 roku powstał WebCrawler, pierwsza wyszukiwarka oferująca użytkownikowi wyszukiwanie pełno tekstowe. Produkt ten jest dostępny, aż do dnia dzisiejszego pod adresem: http://www.webcrawler.com .

W tym samym roku powstała kolejna, znana aż do dzisiaj, wyszukiwarka o nazwie Lycos dostępna pod adresem http://www.lycos.com.

Niedługo po niej powstały kolejne wyszukiwarki walczące o popularność takie jak:  Magellan, InfoseekInktomi, Northern Light i AltaVista. Najpopularniejszą w wyszukiwarką w tamtym okresie stało się Yahoo! . Wyszukiwarka  została wykonana przez dwóch studentów Uniwersytetu Stanforda, Jerrego Yanga oraz Davida Filo. Jej początkową nazwą było David and Jerry’s Guide to the World Wide Web i była niczym więcej jak hierarchicznie uporządkowanym katalogiem stron internetowych tworzonym ręcznie przez jej autorów. Yahoo! była jedną z pierwszych wyszukiwarek (a zarazem portali) internetowych, której udało się zarobić ogromne pieniądze na reklamie.

Kolejną walczącą o pozycję i uznanie (i pieniądze) firmą było Excite. Jej założycielami byli Graham Spencer, Joe Kraus, Mark Van Haren, Ryan McIntyre, Ben Lutch i Martin Reinfried. Wszyscy byli studentami Uniwersytetu Stanforda.

Rynek wyszukiwarek internetowych stał się bardzo dochodowy. Generował on miliony dolarów zysku pochodzącego z reklam. Firmy były tak skupione na umieszczaniu reklam na łamach swoich portali internetowych, że zapomniały o swoim podstawowym celu jakim było dostarczanie wysokiej jakości wyników wyszukiwania.

W roku 1996 pojawił się produkt, który miał zrewolucjonizować rynek wyszukiwarek internetowych oraz mieć wpływ na przyszłość Internetu. Tym produktem była wyszukiwarka Google. Jej nazwa pochodziła od przestawienie słowa googol oznaczającego liczbę 100 podniesioną do potęgi setnej.  Jej wynalazcami byli  doktoranci Uniwersytetu Stanforda: Larry Page i Sergey Brin. Kluczem do sukcesu ich wynalazku było wykorzystanie autorskiego algorytmu oceniania jakości stron PageRank (Page odnosi się do nazwiska wynalazcy Larry’ego Page’a). Szczegóły algorytmu są mocno strzeżoną tajemnicą firmy, ale ogólna zasada działania polega na ocenie jakości strony poprzez zbadanie ilości stron powołujących się na nią oraz ich jakości. Google od początku swojego powstania (w przeciwieństwie do konkurencji) nie zamieszczał reklam na swojej stronie głównej. Sposobem na zarobieniu fortuny na reklamie w sposób nie utrudniający życia użytkownikowi było zastosowanie linków sponsorowanych. Polegały one na umieszczaniu strefy płatnych wyników wyszukiwania znajdujących się nad i pod wynikami „organicznymi” oraz po ich prawej stronie, przy krawędzi ekranu.

Od czasu powstania wyszukiwarka Google’a bardzo się rozwinęła i wprowadziła wiele nowych funkcjonalności. Początkowo wspierała ona tylko wyszukiwanie informacji tekstowych znajdujących się na stronach internetowych. Obecnie Google udostępnia nam ogrom możliwości począwszy od wyszukiwania zdjęć, wideo, map, wiadomości, a kończąc na najpopularniejszej na świecie darmowej poczcie internetowej, dokumentach on-line i wielu, wielu innych.

Mamy za sobą ponad 20 lat historii wyszukiwarek internetowych. Obecnie dostępne produkty w niczym nie przypominają swoich protoplastów. Oferują nam niewyobrażalny ogrom informacji, dostępny na kliknięcie myszki. Mało kto wyobraża sobie dziś życie bez Internetu, a tym bardziej życie bez takich dobrodziejstw technologicznych jak wyszukiwarka internetowa. Na dodatek rozwój wyszukiwarek nie zatrzymał się, lecz ciągle idzie naprzód dając nam, użytkownikom, coraz więcej zaskakujących i spektakularnych możliwości. Cieszmy się więc i przeszukujmy czeluści Internetu bogatsi tę wiedzę. Ku chwale wyszukiwarek!

Autor: 83786

Źródła:
http://www.youtube.com/watch?v=iBCSibI4ffg
http://www.youtube.com/watch?v=dx8fS_scMS0
http://www.youtube.com/watch?v=Nl3iRZ7PAKU
http://pl.wikipedia.org/wiki/Wyszukiwarka_internetowa

Reklamy
Styczeń 2, 2012

- autor: tsissput

Wyszukiwanie najważniejszych osób w sieci na podstawie artykułu „Identifying sets of key players in a social network”

 

Wstęp

Artykuł dotyczy wyszukiwania najważniejszych indywiduów w ramach sieci społecznej. Z uwagi na specyfikę tematu, wpis w przeważającej części przybliża treści wyrażone w dokumencie „Identifying sets of key players in a social network” S.Bogratti’ego.

Głównym założeniem jest fakt, że optymalny wybór kluczowych osób (k kluczowych elementów tworzących zbiór K) zależy od tego, w jakim celu przeprowadza się wyszukiwanie. W zależności od celu, można wyróżnić 2 odmiany problemu – KPP-POS (Key Player Problem / Positive) oraz KPP-NEG (Key Player Problem / Negative).

 

Zdefiniowanie problemu

Problem kluczowych graczy w formie NEG dotyczy stopnia zależności sieci od jej kluczowych elementów. Innymi słowy chodzi o utrzymanie spójności grafu. Istotą jest pomiar ważności zerwanych powiązań – ilościowa miara redukcji spójności sieci, która nastąpiłaby, gdyby usunąć dane węzły. Dla zobrazowania problemu, jako praktyczny przykład można tu podać wybór zbioru z populacji w celu uodpornienia lub przeprowadzenia kwarantanny w toku powstrzymywania rozwoju epidemii. Innym przykładem może być zneutralizowanie (np. aresztowanie) określonych członków środowiska przestępczego w celu największego utrudnienia przeprowadzania zorganizowanych akcji przestępczych.

W drugim sformułowaniu problemu (KPP POS) mówimy raczej o stopniu w jakim kluczowi gracze są połączeni i osadzeni w sieci istniejącej wokół nich. Idąca za tym podejściem intuicja jest następująca: wybieramy mały podzbiór populacji, w celu rozpropagowania na jak największą część populacji odpowiednich zachowań / przekonań – np. wybór osób, które będziemy zachęcać, aby promowały zdrowy tryb życia. We wszystkich wspomnianych sytuacjach szukamy zbioru wierzchołków (indywiduów) grafu (społeczności), które są optymalnie rozstawione, aby szybko rozproszyć informację / nastawienia / zachowania / dobra.

Formalnie problem wyszukiwania kluczowych obiektów można zdefiniować następująco. Dana jest sieć społeczna (w reprezentacji nieskierowanego grafu). Celem jest znalezienie zbioru k wierzchołków takiego, że:

  1. (KPP-Neg) usunięcie wybranego zbioru będzie skutkowało w sieci wynikowej najsłabszą możliwą spójnością
  2. (KPP-Pos) wybrany zbiór jest w jak największym stopniu połączony ze wszystkimi pozostałymi wierzchołkami grafu

Pozostaje jeszcze kwestia kluczowych pojęć – najsłabszej możliwej spójności oraz największego stopnia połączenia. Zostaną one opisane dalej. W uproszczeniu można powiedzieć, że NEG doprowadza do fragmentacji sieci na komponenty lub też prowadzi do takiego wydłużenia odległości między wierzchołkami, aby były one rozpatrywane jako nie połączone ze sobą. Z kolei POS polega na wyszukiwaniu wierzchołków, z których można osiągnąć tak wiele z pozostałych, jak to tylko możliwe przy użyciu bezpośrednich połączeń lub krótkich ścieżek.

Nie jest łatwo wypracować ogólne metody dla każdego z tych problemów z uwagi na różnorodność sformułowania kluczowych pojęć. Niemniej Bogratti podejmuje próbę skonstruowania generycznych rozwiązań wspomnianych problemów.

Na pierwszy rzut oka obydwa problemy wydają się być łatwe do rozwiązania poprzez wybór odpowiednich miar centralności węzłów i wyboru k najbardziej zcentralizowanych. Alternatywnie można skorzystać z podejść znanych z teorii grafów. Napotykamy jednak 2 powody, dla których takie rozwiązania nie spisują się dobrze. Jednym z nich jest kwestia celu. Mianowicie dotyczy to faktu, iż miary centralności nie są zaprojektowane ściśle dla jednego z dwóch problemów (NEG/POS) i stąd nie muszą prowadzić do rozwiązań optymalnych. Drugim istotnym czynnikiem jest kwestia zbioru. Mianowicie obydwa sformułowania problemu dotyczą wyboru zbioru wierzchołków a nie indywiduów, a optymalny zbiór dla dowolnego zadania niekoniecznie składa się z k najbardziej optymalnych obiektów rozważanych indywidualnie.

 

Kwestia celu

Dla problemu NEG najbardziej odpowiednią miarą centralności jest betweenness Freeman’a, która jest miarą sumy proporcji liczby najkrótszych ścieżek od jednego wierzchołka do innego przechodzących przez dany węzeł, do wszystkich wspomnianych najkrótszych ścieżek niekoniecznie przez ten węzeł przechodzących. Wierzchołek z wysokim współczynnikiem tej miary jest na najkrótszej ścieżce między wieloma parami węzłów i jego usunięcie powoduje to, że wiele par węzłów traci połączenie lub przynajmniej ich połączenie jest dłuższe.

Optymalność tego współczynnika dla wyszukiwania wierzchołków, których usunięcie z sieci spowoduje największą redukcję spójności nie jest jednak gwarantowana dla typowych definicji spójności. Wierzchołek 1 grafu z fig.1 charakteryzuje się największą miarą centralności dla każdej standardowej miary włącznie z betweenness. Usunięcie wierzchołka 1 nie skutkuje jednak rozłączeniem sieci. Odległości między wierzchołkami rosną ale jeśli fragmentacja jest celem, to usunięcie wierzchołka 1 jest nieefektywne. Z kolei usunięcie elementu 8 mającego mniejszą centralność (dla wszystkich miar) powoduje rozłączenie grafu – podział na 2 części.

Inspirację można odnaleźć w teorii grafów. Dla przykładu wiele zostało zrobione w kwestii wrażliwości grafów na rozłączenie, co bezpośrednio odpowiada sformułowaniu problemu KPP-NEG.

Przechodząc do wersji POS, jeśli sformułujemy problem jako szukanie wierzchołka, z którego można osiągnąć bezpośrednio najwięcej innych wierzchołków, prosty stopień centralności jest dodatkowo optymalny. Z kolei jeśli podejdziemy do problemu z celem dotarcia do jak największej liczby węzłów w określonej liczbie kroków, najbardziej odpowiednią miarą centralności będzie kolejna z 4 miar centralności szeroko używanych w analizie sieci – closeness centrality. Jest ona zdefiniowana jako suma odległości od danego węzła do wszystkich innych. Dla fig.2 węzeł 4 ma najlepszą wartość tego współczynnika. Jednakże, jeśli interesuje nas dotarcie do największej liczby wierzchołków spośród występujących na ścieżkach o długości <= 2, węzeł 3 będzie lepszym wyborem (da się z niego dotrzeć do 8 wierzchołków a z 4 do 6 elementów).

Kwestia zbioru

Kwestia centralności zbioru dotyczy tego, że wybór k wierzchołków jako zbioru, które razem są optymalnym rozwiązaniem problemów POS i NEG, jest czym innym niż wybór k wierzchołków, które rozpatrywane oddzielnie są optymalne.

Rozważmy problem NEG. Na fig.3 wierzchołki h oraz i są indywidualnie najlepszymi kandydatami do usunięcia w celu podzielenia sieci. Jednakże pozbycie się wierzchołka i po wcześniejszym usunięciu h, nie skutkuje większą fragmentacją (zgodnie ze stosowanymi miarami) niż po usunięciu jedynie wierzchołka i. Z kolei wierzchołek m nie jest indywidualnie tak silny (effective) jak wierzchołek i, w oddzielonych parach wierzchołków, ale usunięcie m oraz h powoduje większą fragmentację niż usunięcie samego m lub h. Powodem, dla którego i oraz h razem nie są tak dobrą parą kandydatów jak h i m, jest to, że i oraz h są nadmiarowe w odniesieniu do ich współpracy – centralność jednego jest po części centralnością drugiego (ich centralności są zależne względem siebie). Stąd łączna centralność zbioru jest mniejsza niż suma centralności wszystkich elementów tego zbioru.

Prawo nadmiarowości ma rację bytu również w problemie POS. Rozważając fig.4 wierzchołki a oraz b są indywidualnie najlepszymi łącznikami. Każdy z nich sąsiaduje z 5 innymi wierzchołkami. Liczność sumy zbiorów sąsiadów dla tych wierzchołków jest równa także 5, czyli wspólnie nie osiągają one więcej sąsiadów niż każdy z osobna. Dla przykładu, gdyby parą były wierzchołki a oraz c (który indywidualnie sąsiaduje jedynie z 3 wierzchołkami), sąsiedztwo grupy {a, c} byłoby maksymalne – obejmowałoby każdy wierzchołek w sieci. Przyczyną osiągania przez {a, c} lepszego wyniku niż {a, b} jest fakt, że a oraz c są mniej podobne do siebie strukturalnie (biorąc pod uwagę strukturę ich połączeń) niż a i b. Takie podobieństwo strukturalne dotyczy stopnia pokrywania się sąsiedztw wierzchołków. Strukturalnie podobne wierzchołki, z definicji są nadmiarowe z uwagi na sąsiedztwo oraz odległości. Różnica polega na tym, że nadmiarowość dla POS rozpatruje się z uwagi na odległość oraz sąsiedztwo, podczas gdy dla NEG biorąc pod uwagę uzupełnianie się (np. linkowanie do tych samych komponentów).

Proponowane rozwiązanie

KPP-NEG – Fragmentacja

Kluczowym pojęciem w tym problemie jest podział grafu. Do rozwiązania tego problemu potrzebna jest zatem bezpośrednia miara podziału grafu. Dysponując taką miarą możemy ocenić każdy zbiór wierzchołków określając jak dobrym rozwiązaniem problemu KPP-Neg jest on. Prawdopodobnie najbardziej oczywistą miarą fragmentacji sieci jest liczba komponentów (zbiorów wierzchołków odizolowanych od innych zbiorów). Np. dla 1 komponentu, sieć nie jest podzielona. Największa fragmentacja występuje, kiedy każdy wierzchołek jest odizolowany od pozostałych (liczba komponentów = liczba wierzchołków). Dla wygody normalizujemy liczbę przez podzielenie przez liczbę wierzchołków.

Problem z tą miarą jest taki, że nie uwzględnia ona rozmiarów komponentów. Dla przykładu – na fig.3 usunięcie węzła m lub i powoduje podział sieci na 2 części. W pierwszym przypadku większość węzłów pozostaje połączona, natomiast w drugiej sytuacji istnieje znacznie więcej par, gdzie nie występuje połączenie między wierzchołkami. To prowadzi do zastosowania innej miary stopnia podziału sieci, która polega na zliczaniu liczby par węzłów, które są rozłączone. W tym celu oblicza się macierz R, w której element r_{ij}=1, jeśli z i można przejść do j, oraz 0 w przeciwnym wypadku. Miara jest zdefiniowana następująco:   F=1-\frac{2 \sum_i \sum_{j<i} r_{ij}}{n(n-1)}

Z kolei problemem związanym z tą miarą jest koszt obliczeń. Dla przyspieszenia można skorzystać z faktów, że węzły wewnątrz komponentów są wzajemnie osiągalne a komponenty grafu mogą być przetwarzane wydajniej. Miara F może być zatem policzona bardziej ekonomicznie przez rozważanie komponentów z uwzględnieniem ich rozmiarów (s_k – rozmiar k-tego komponentu).    F=1-\frac{\sum_k s_k (s_k - 1)}{n(n-1)}

Miara F jest bardzo podobna do współczynnika koncentracji – wskaźnika Herfindahla-Hirschmana, w tym kontekście przyjmującego następującą postać:    H=1-\sum_k (\frac{s_k}{n})^2

Obie miary (F i H) osiągają minimum w 0 (dla 1 komponentu), lecz miara H osiąga wartość maksymalną 1 - \frac{1}{n} kiedy sieć jest maksymalnie podzielona. Normalizując H, przez podzielenie przez jej wartość maksymalną, otrzymujemy miarę F.

Alternatywną miarą jest entropia, która w tym zastosowaniu wygląda następująco:    E=-\sum_k \frac{s_k}{n}\ln \frac{s_k}{n}

Ponownie napotykamy na problem z zakresem wartości (<0;∞>) . Aby sobie z tym poradzić, możemy podzielić wartość miary przez wartość dla sytuacji, gdzie każdy wierzchołek jest odizolowany od pozostałych. Otrzymujemy wówczas następującą miarę:   E=-\frac{ \sum_k \frac{s_k}{n}\ln \frac{s_k}{n} }{ \sum_k \ln \frac{s_k}{n} }

Podczas gdy miara fragmentacji F, oraz entropia E są bardzo satysfakcjonujące w tym zastosowaniu, nie biorą one pod uwagę kształtu komponentów – ich wewnętrznej struktury. Rozważmy sieć składającą się z 2 części, każda rozmiaru 5 będąca kliką (fig.5a). Sieć ta jest postrzegana pod względem podziału tak samo jak sieć składająca się z 2 części 5 elementowych będących „linią” (fig.5b). W tej drugiej sieci odległości są znacznie większe niż w pierwszej. Wiadomo jednak (Granovetter, 1973), że wierzchołki nie muszą być rzeczywiście rozłączone aby być praktycznie rozłączone – jeśli odległości między nimi są wystarczająco długie, wierzchołki są efektywnie oddzielone od siebie.

W dodatku napotykamy jeszcze jeden problem. W niektórych przypadkach wymagany rozmiar zbioru kluczowych elementów jest  tak mały, że nie istnieje zbiór tego rozmiaru rozdzielający graf. Ciągle preferujemy jednak metody oceniania które zbiory są lepsze od innych pod względem możliwości „prawie rozłączenia” wielu par wierzchołków.

Oczywistym rozwiązaniem jest pomiar całkowitej odległości między wszystkimi parami wierzchołków i uwzględnienie go jako miary wirtualnego rozdzielenia. Jednakże działa to tylko w przypadku, gdy graf pozostaje połączony. W przeciwnym przypadku musielibyśmy sumować nieskończone odległości. Praktyczną alternatywą jest oparcie miary o sumę odwrotności odległości. W tym przypadku powstaje wersją miary F, w której wagi to odwrotności odległości. Wartość rij  zostaje zastąpiona przez \frac{1}{d_{ij}}, co oddaje stopień osiągalności wierzchołka j z i, mieszczący się w przedziale <0;1> .      F^D=1-\frac{2\sum_{i>j}\frac{1}{d_{ij}}}{n(n-1)}

Miara F^D jest odpowiada mierze F, gdy wszystkie komponenty są klikami. Kiedy odległości wewnątrz komponentów są większe niż 1, miara bierze pod uwagę względną spójności komponentów. Dla przykładu graf z fig.5b, który jest mniej spójny niż graf na fig.5a ma większą miarę F^D .

KPP-POS: spójność wewnątrz zbioru

Fundamentalnymi pojęciami są w tym wypadku połączenia lub spójność między elementami zbioru kluczowych wierzchołków a pozostałymi elementami grafu. W celu rozwiązania problemu, potrzebna jest bezpośrednia miara liczby połączeń między wybranym zbiorem oraz pozostałą częścią grafu. Dążymy zatem do zdefiniowania funkcji, która oddawałaby spójność między tymi 2 podzbiorami. Na początek zdefiniujmy miarę, w której aij=1 , jeśli wierzchołki i oraz j sąsiadują ze sobą i 0 w przeciwnym przypadku:   C_K=\sum_{i\in K, j\in {V-K}}a_{ij}

To proste podejście ignoruje strukturalną równoważność elementów zbioru, przede wszystkim podwójnie zliczane powiązania do tych samych indywiduów. Zamiast tego chcemy zdefiniować nieco bardziej wyrafinowaną miarę, jak następująca:      C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} a_{ij}

Gdzie operacja sumy mnogościowej jest nieokreśloną dokładnie funkcją agregacji, jak minimum lub maksimum. Dla funkcji max miara reprezentuje liczbę unikalnych wierzchołków spoza zbioru K, do których elementy z K są sąsiednimi. Jest to równoważne stopniowi centralności grupy Everetta i Borgattiego.

Idąc dalej, chcielibyśmy ponownie – tak jak dążyliśmy do tego przy fragmentacji – aby następna miara odpowiednio radziła sobie z odległościami. Przyczyna jest taka sama jak poprzednio – 2 grupy znanego rozmiaru mogą być sąsiadujące z taką samą liczbą wierzchołków, i jednocześnie dla jednej z grup nieosiągalne z niej wierzchołki mogą być odległe o jedno połączenie, a dla innej mogą być bardzo odległe. Prostym podejściem jest miara m-osiągalności, w której zastępujemy sąsiedztwo osiągalnością, tak, że rijm=1  jeśli z i można osiągnąć j, przy scieżce o długości <= m, 0 wpp. Ponownie dla sumy mnogościowej będącej funkcją max, miara m-osiągalności może zostać przedstawiona następująco:     C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} r_{ij}^m

M-osiągalność jest wtedy liczbą unikalnych wierzchołków osiągalnych przez dowolny wierzchołek ze zbioru K, przy odległości <= m połączeń. Zaletą tej miary jest łatwość interpretacji. Wadą z kolei jest to, że zakłada ona, że wszystkie ścieżki o długości <= m, są tak samo ważne, oraz że wszystkie ścieżki o długości >m są nieistotne.

Bardziej wrażliwą miarą jest osiągalność ważona odległościami, czyli suma odwrotności odległości od elementów zbioru K do wszystkich pozostałych wierzchołków, gdzie dla zbioru wierzchołków brana jest minimalna odległość:     C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} \frac{1}{d_{ij}}

Dla jasności interpretacji warto rozważyć wszystkie odległości wewnątrz zbioru elementów kluczowych jako jednakowe i sumować je dla wszystkich wierzchołków. Warto również znormalizować miarę do przedziału <0;1> . Można również uprościć notację przez zdefiniowanie dKj  – minimalnej odległości od dowolnego wierzchołka ze zbioru K, do wierzchołka j, co skutkuje ostateczną postacią miary:     D_R= \frac{\sum_j \frac{1}{d_{K_j}}}{n}

Łatwo można dostrzec, iż formuła ta to ważona proporcja wszystkich wierzchołków osiągalnych z danego zbioru, gdzie wierzchołki są ważone odwrotnie proporcjonalnie do ich minimalnej odległości od zbioru, a tylko wierzchołki o odległości 1 mają pełną wagę. Stąd D_R osiąga max (1) kiedy wszystkie zewnętrzne wierzchołki są sąsiednie do przynajmniej 1 ze zbioru K. Wartość min (0) jest z kolei osiągana, gdy żaden wierzchołek z K nie należy do tego samego komponentu co jakikolwiek wierzchołek spoza K (np. zbiór K jest zupełnie odizolowany).

Wybór zbioru K poprzez optymalizację kombinatoryczną

Podczas gdy prosta heurystyka polegająca na wybieraniu kluczowych k elementów nie zdaje egzaminu, musimy znaleźć inny sposób na skompletowanie zbioru K. Jedno podejście polega na poszukiwaniu modyfikacji wspomnianej heurystyki, która eliminowałaby słabe punkty swojej poprzedniczki. Dla przykładu można zacząć od znalezienia kluczowego wierzchołka i następnie dodawać kolejne najlepsze indywidua, będące najmniej nadmiarowymi w zestawieniu z dotychczas wybranymi. Innym sposobem jest jednoczesny wybór k elementów zbioru K przy pomocy optymalizacji kombinatorycznej. Jest to rozwiązanie sugerowane.

Reprezentując rozwiązanie problemów POS / NEG jako łańcuch S, składający się z zer i jedynek, gdzie 1 oznacza, iż wierzchołek i jest elementem proponowanego zbioru K (0 wpp), łatwo można zastosować algorytmy optymalizacyjne takie jak tabu-search, K-L, simulated annealing, lub algorytmy genetyczne do znalezienia S. Wstępne eksperymenty sugerują, że wszystkie ze wspomnianych typów algorytmów radzą sobie doskonale z KPP. Poniżej zaprezentowano przykładowe rozwiązanie oparte na prostym algorytmie greedy. Jest ono wykonywane wiele razy na losowych zbiorach startowych.

  1. Wybierz k losowych wierzchołków do zbioru K
  2. Dopasuj F używając odpowiedniej metryki
  3. Dla każdego węzła u w zbiorze K i każdego v spoza zbioru K
    1. \Delta F = polepszenie dopasowania po zamianie u z v
    2. Wybierz parę z najlepszym \Delta F
      1. Jeśli \Delta F \leq F zakończ
      2. Wpp zamień u z v (parę z najlepszym \Delta F) i ustaw F = F + \Delta F
      3. Idź do kroku 3.

Przykład

Działanie algorytmów zostanie następnie przedstawione na krótkim przykładzie. Wykorzystany zbiór danych (fig.7) to sieć powiązań pomiędzy znanymi terrorystami. Graf składa się z 74 wierzchołków – podejrzewanych terrorystów. Do celów analizy wykorzystujemy jedynie główny komponent sieci – składający się z 63 indywiduów.

Pierwsze pytanie, jakie należy zadać (KPP-NEG) to: które osoby powinny zostać odizolowane aby maksymalnie poprzerywać sieć? Załóżmy, że możemy unieszkodliwić 3 osoby.

Uruchomienie algorytmu z użyciem miary F, wybiera 3 węzły oznaczone na czerwono (A, B, C). Usunięcie tych wierzchołków skutkuje fragmentacją z wartością miary 0.59 i przerywa graf na 7 komponentów (włącznie z 2 dużymi tworzącymi lewą i prawą połowę grafu).

Drugim pytaniem przed jakim stajemy (KPP-POS) jest: „wiedząc, że chcemy rozproszyć pewną informację, których obiektów powinniśmy użyć aby ta informacja szybko i niezawodnie dotarła do wszystkich wierzchołków?”. Załóżmy, że informacja po przebyciu więcej niż 2 połączeń jest bezużyteczna (zostaje wykryta lub ulega destrukcyjnej modyfikacji). Stąd, szukamy najmniejszego zbioru wierzchołków, z pomocą którego możemy dotrzeć do wszystkich węzłów grafu używając połączeń o długości <= 2. Rozwiązanie znalezione przez algorytm to 3 wierzchołki – zaznaczone na rys.7 jako kwadratowe (A, C, D) – pozwala na dotarcie do wszystkich wierzchołków sieci.

Podsumowanie

W artykule został zdefiniowany problem wyboru kluczowych graczy w dwóch odmianach, wraz z uwzględnieniem kwestii celu oraz zbioru. Zostały także przedstawione rozwiązania oparte na teorii grafów, a także problemy związane z różnymi podejściami. Zaprezentowano także przykład, ukazujący, iż zaproponowane algorytmy radzą sobie bardzo dobrze z tak zdefiniowanymi problemami. Problem kluczowych indywiduów może znaleźć szerokie zastosowania w wielu dziedzinach nowoczesnej nauki.

Autor: 84879

Źródło: Stephen P. Borgatti, „Identifying sets of key players in a social network”