Modelarea unui arbore ca structura de date cu persoanele infectate – Contact-Tracing COVID-19 [Part-1]

O dilemă pentru interpretarea rezultatelor obţinute prin contact-tracing în diferite soluţii de software dezvoltate, şi tot odată pentru tot proiectul Google legat de Contact Tracing prin Bluetooth LE, după părerea mea este modul în care s-ar construi mesh-ul ce indică parcursul infectării.

Dacă se considera ca abordare de construcţie structura de date tip arbore am avea pacientul infectat ar putea fi rădăcina, nodurile pe unde a plecat în nivelul inferior şi frunzele oamenii unde s-a incheiat infecţia generată de rădăcină. Astfel, dacă se stabileşte un device al unei persoane infectate p1 după extragerea datelor legate de proximitatea lui în ultima lună se poate parcurge arborele spre noduri(persoane ce au intrat in contact) p2, p3 -> şi care cel mai probabil vor fi şi ele infectate formând astfel sub arbori şi trebuie analizaţi şi acei sub arbori care ar putea fi infectaţi în x zile depinzând de când proximitatea a fost stabilită. Aici ar mai interveni şi problema când în acelaşi subarbore s-ar găsi persoane posibile infectate comune cu un alt subarbore derivat din alt nod părinte. Foarte important sunt şi frunzele de stabilit adică persoanele ce nu au mai intrat în contact cu nimeni pentru că la ele să se puncteze că acolo e finalul unui arbore sau sub arbore. Pe această topologie urmăritul infectărilor prin nod-uri devine extrem de dificil, dar depinde cum sunt traversate, adâncime sau pe lăţime din punct de vedere al variabilei de timp.

Persoana1 porneşte infecţia, o trimite mai departe spre persoana2, mai apoi spre persoana3.
Persoana2 devine nod rădăcină la rândul ei pentru persoana 5 si persoana 6.
Persoana 3 devine nod rădăcină pentru persoana4.
Persoanele: 4, 5, 6 termină subarborele devenind frunze şi nu duc infecţia mai departe.

Stabilind ora şi ziua în care două persoane au intrat în contact e extrem de important pentru a se stabili ordinea infectării. Am adăugat câteva ore ce sunt exact în ordinea în care şi persoanele sunt legate. Se poate observa că pentru un exemplu simplu ordinea şi aşa e destul de dificil de menţinut din cauza orelor apropiate sau din cauza faptului ca aparţin aceleiasi zile. Dacă am adăuga mii de persoane în structură deja ar deveni extrem de greu de menţinut.

Am considerat un arbore ca exemplu pentru ca merg pe principiul că niciun nod, sau copil al nodului nu va avea o dublă legătură ci doar una, unidirecţională. Dacă există cumva bidirecţionale am merge pe o structură de date tip graf direcţional sau non direcţional în care nu am şti exact nodurile ci doar un vârf terminal(persoana infectată) care ar putea fi vârf în alt subgraf. Ideea că ar putea fi orientate sau neorientate, adică de la un vârf la altul să fie posibilă o dublă conexiune pe aceeaşi muchie ori doar una într-un sens pe o muchie definit de cei ce validează vârful infectat spre vârful neinfectat încă. Legăturile între persoanele infectate nu sunt neapărat întotdeauna într-o direcţie, pentru ca dacă P1 ar fi infectat şi ar infecta P2, P2->P3 , s-ar putea ca la un moment dat P3 să intre în contact cu P1 direct. Dar e extrem de important pentru a se stabili dacă P3 a mai intrat cândva în legătură cu P1, pentru a se cunoaşte daca pentru P3 trebuie creată muchie spre P1. De accea consider că ceva orientat e esenţial pentru a se stabili dacă o persoană s-a mai întâlnit cândva cu cineva din lanţul creat de el şi când.

O altă problemă pe care o consider eu este că acele chei de diagnoză vor fi urcate de rădăcina unui arbore de infecţii, să presupunem, adică de prima persoană infectată. Dar în cazul în care celelalte noduri de sub au creat deja alţi subarbori şi au schimbat chei de proximitate în intervalul de când au întâlnit persoana 1 cheile lor posibile infectate sunt deja la următoarele persoane când primesc notificarea că s-ar putea să se fi întâlnit cu cineva infectat acum o zi.

Am creat o structură explicând această situaţie în care prin nodul 2 se apucă să se transmită infecţia spre p4, iar p4 spre p5 şi p6 în timpul în care p1 e diagnosticat şi cheile lui sunt uploadate şi se începe procesul de fetching. Considerăm p1 s-a întâlnit luni cu p2 la ora 07:55am spre care a trimis 2 chei pentru că cei doi au stat în proximitate cam 30minute. P1 se întâlneşte şi cu p3 luni la ora 12:05pm căruia îi trimite 3 chei, 45minute. În ziua de marţi p2 se întâlneşte cu p4 la ora 11:05am şi schimbă 4 chei, p4 la rândul lui se întâlneşte cu p5 la ora 14:33pm şi cu p6 la ora 15:20pm, schimbând 5 chei cu amândoi. Tot marţi p3 intră în proximitate cu p7 la 18:30 cu care schimba şi el 1 cheie.

Bun, având aceste date problema se pune în felul următor. Când p1 e diagnosticat marţi la 19:00 şi i se urcă toate cheile zilnice de diagnoză, p2 a schimbat deja cheile lui zilnice cu p4 care rândul lui a schimbat cheile private zilnice cu p5 şi p6. Iar p3 a schimbat chei zilnice cu p7. Se începe procesul de fetching a cheilor lui p1 în toate device-urile personale.. p2 vede la ora ~20:00(depinde de delay) o notificare cum că 2 chei primite luni sunt chei de diagnoză şi că s-ar putea să fie şi el posibil infectat. Aici google zice că persoanei ăsteia i se va propune ceva în funcţie de aplicaţia serviciului medical. Bun, dar asta după părerea mea nu e de ajuns. Dacă cumva p2 decide să nu ia în seamă el întrerupe mersul parcurgerea arborelui înspre posibilul infectat sub arbore p4->p5, p4->p6. Astfel p4, p5, p6 nu vor şti până în ultima clipa(urmatorul fetching) când vor fi declaraţi infectaţi, asta în cazul de faţă exclusiv pe exemplul dat, deoarece există şansa ca p5 ori p6 să aibă chei de diagnoză de la altcineva, după cum explicam în structura tip graf. Soluţia ar fi ca în acea notificare p2 să fie întrebat dacă e de acord să urce şi el cheile lui din ultimele x zile astfel se poate parcuge şi subarborele derivat din nodul p4, care la rândul lui va fi notificat şi întrebat daca doreşte să urce cheile de proximitate pentru a notifica p5 şi p6. Practic s-ar parcurge ca un efect de domino în care toate piesele trebuie să îşi facă partea dacă se vede legătura dintre ele. Dacă una nu îşi face treaba, celelalte habarn-au ce să facă. Consider şi cazuri nu prea complicate având în vedere că majoritatea lumii ar fi în carantină deci nu prea se poate intra în contact cu multe persoane.

Trebuie adoptata si o soluţie pentru cei care sunt notificaţi că au 2 chei ce se potrivesc cu chei de diagnoză din ziua x să îşi poată lăsa la rândul lor cheile private pe care le-au trimis înspre alte persoane. Pentru că dacă se aşteaptă o zi, două, trei până când persoana ce a primit notificarea merge spre un spital şi după confirmare îşi va urca şi el cheile, celelalte persoane nu vor fi anunţate în timp util. Adică treaba merge între Alice şi Bob cum explică Google într-o diagramă, că bob e diagnosticat şi îşi urcă cheile cu acordul lui pe un server. Alice observă o notificare cum că are 2 chei de la cineva şi că e posibil infectată şi “Additional information is provided by the health authority app or website”, textul oferit de Google. Ceea ce e egal cu 0 pentru atunci când intervine şi Maria în schemă, şi alţi zeci sute de oameni cu legătură cu Bob.

Structura e pur demostrativă, deja pentru ~10 persoane situaţia devine destul de încâlcită pe măsură ce se construiesc alţi arbori. Pentru a ţine totul în clar toate legăturile trebuie parcurse în ordine cronologică. Eu am pus persoanele in ordine aici, insa aceasta ordine trebuie definită de la începutul construcţiei arborelui.

La fel şi după ce o infecţie e marcată într-un arbore, se stabilesc noduri, frunze terminale e foarte important ca fiecare element sa fie tranzitionat cumva prin cele 3 stari ca expus->infectat->vindecat. Tranziţia aceasta se poate observa în structură atunci când cheile sunt schimbate la zile mai îndepărtate în cadrul unei luni. In exemplele pe care le-am prezentat am considerat un interval extrem de mic in două zile.

Daca s-ar modela printr-o structura de date de tip graf ceea ce ar fi extrem de important e sa se stabilească data, ora ca un graf orientat/neorientat sa prinda contur. Dar avantajul unei structuri de tip graf este ca poate stabili o legatura chiar si bidirectionala intre doi indivizi si se pot alcatui diferite repetitii ale legaturilor(cicluri).

Un viitor articol va cuprinde si aceasta analiza pe un graf.

Add a Comment

Your email address will not be published. Required fields are marked *