W ostatnich latach mamy burzliwy wzrost dyscypliny Machine learning. Między innymi nauczyliśmy się analizować obrazy przy użyciu sieci neuronowych. Teraz przyszła kolej na analogiczne podejście do grafów. To bardzo świeża dyscyplina, a jej stan dość aktualny można zobaczyć na wykładach, które Jure Leskovec (chief scientist w Pinterest) prowadził na Stanfordzie w 2019 r. Poniżej prezentuję koncepcję rekonstrukcji genealogii (grafu społecznego) wyższych warstw społeczeństwa polskiego w latach 1788-1939. Poszukuję chętnych do współpracy przy tym projekcie.
Graf genealogiczny jest bardzo charakterystyczny. Wywód przodków każdej osoby jest binarny: mamy ojca i matkę, oni z kolei także mają ojca i matkę itd.
Załóżmy, że badamy grupę osób, które były istotne dla społeczeństwa polskiego w roku 1938. Wtedy ukazał się przewodnik biograficzny pod red. Stanisława Łozy, Czy wiesz, kto to jest?. Zawiera on dane biograficzne 4862 osób aktywnych w tym czasie (i wartych, by je znać). Dla 4802 z nich znamy datę urodzin – jest to średnio 1886 r. Jedno pokolenie trwa między 25 a 33 lata (3-4 pokolenia na stulecie). Zatem w roku 1788 rodzą się ich dziadkowie lub pradziadkowie. Jeżeli uwzględnimy ich rodziców, to możemy przyjąć że do opisu genealogii każdej z tych osób wystarczy graf zawierający w najdalszym pokoleniu 2^5=32 osoby, a wraz z osobą opisywaną (probantem) i pokoleniami pośrednimi – 63 osoby.
Gdybyśmy nie mieli utożsamień (gdyby wśród osób opisanych u Łozy nie było żadnych osób spokrewnionych ze sobą), to znając kompletną ich genealogię do 5. pokolenia uzyskujemy 4862 grafy składające się z 63 węzłów, łącznie więc jest 306.306 węzłów (osób).
W drugim skrajnym przypadku, gdyby te 4862 osoby miały wspólnego ojca i matkę, mielibyśmy tylko 4862+62=4924 węzły. W rzeczywistości ich liczba była pośrednia.
Każde dwa węzły możemy utożsamić. Możemy stworzyć macierz zawierającą 306.306 wierszy i tyleż kolumn. Utożsamienia są symetryczne, łącznie mamy więc (306306^2)/2 możliwych utożsamień, więc około 47 mld. To nie jest dużo dla dzisiejszych komputerów. O tym, że genealogia masowa jest w istocie nauką o utożsamieniach, napisałem w moim artykule Genealogia masowa – metodologia tworzenia i publikacji bazy danych, w: Jolanta Sikorska-Kulesza (red.), Edytorstwo wobec masowości źródeł najnowszych, Wydawnictwa Uniwersytetu Warszawskiego, Warszawa 2018, ISBN: 978-83-235-3786-1. Tekst artykułu dostepny tutaj.
W istocie jest tych możliwości dużo mniej. Niektóre możliwości wyklucza sama topologia grafu: nie możemy utożsamiać kobiety z mężczyzną; nie możemy utożsamiać nikogo ze swoim własnym przodkiem.
Dalej: o tym grafie wiemy już bardzo dużo. Dla sporej liczby węzłów znamy ich atrybuty, które wpływają na prawdopodobieństwo ich utożsamienia. W niektórych przypadkach, gdy znamy dokładne daty urodzenia i zgonu lub mamy wiedzę o tym, jak się nazywali – możemy przypisać prawdopodobieństwo 0 lub 1. W innych przypadkach możemy wyliczać prawdopodobieństwo bayesowsko – na podstawie znanego fragmentu grafu możemy ocenić na ile dwóch znanych malarzy żyjących w roku 1938 jest ze sobą spokrewnionych. Możemy też oceniać prawdopodobieństwo, że należy utożsamić jakiegoś urzędnika z członkiem archikonfraterni literackiej w Warszawie itd. itd. Dalej: możemy założyć, że nie utożsamiamy nigdy osób o różnym nazwisku i że wszyscy w linii męskiej noszą to samo nazwisko rodowe (przypadki szczególne możemy później rozstrzygać ręcznie).
Możemy więc działać tak: inicjujemy badanie utożsamień w losowym punkcie. Na podstawie atrybutów węzłów oceniamy prawdopodobieństwo ich utożsamienia. Podejmujemy decyzję losowo na podstawie tego prawdopodobieństwa. Podjęta decyzja powoduje, że pewnym innym utożsamieniom musimy przypisać już automatycznie 0 lub 1. W innych przypadkach „sklejenie” dwóch węzłów sprawi, że nowy węzeł będzie miał sumę atrybutów węzłów „sklejanych”, więc kolejne utożsamienia będą miały inne prawdopodobieństwo.
W ten sposób możemy iterować po całej macierzy uzyskując możliwy graf pokrewieństwa. Możemy takich grafów zrobić więcej a potem wyciągać z nich średnią. Wtedy możemy badać całe polskie społeczeństwo lat 1788-1939 tak jakby było nam znane.
W efekcie uzyskujemy coś podobnego do obrazu historycznego, w którym artysta przedstawił to, co wiadomo, uzupełniając go o własną twórczość tam, gdzie była na to przestrzeń, tak jak w obrazie batalistycznym przedstawiamy znanych dowódców, prawdopodobne rozmieszczenie żołnierzy w pułkach i zupełnie zmyślone (ale możliwe) rozmieszczenie gałęzi na drzewach rosnących wzdłuż drogi.
I to jest prawdziwa socjologia historyczna, a nie to, co nam próbują coniektórzy wcisnąć.
Uzupełnienie:
mnóstwo ciekawych pomysłów o tym, jak generować taki graf (innych niż powyższe) znalazłem w tym oto wykładzie Jure Leskovca (Stanford, jesień 2019):
Tutaj jest artykuł na ten temat: https://arxiv.org/abs/1802.08773
Tu jest PDF z artykułem: https://arxiv.org/pdf/1802.08773
A tutaj repozytorium z programem, który to robi: https://github.com/snap-stanford/GraphRNN