Block, P., Hoffman, M., Raabe, I.J. et al. Social network-based distancing strategies to flatten the COVID-19 curve in a post-lockdown world. Nat Hum Behav (2020). DOI, Nature
Tomo, 9.6.:
Tale članek iz nature human behaviour je kar zanimiv in zelo grafovski. Ideja, da odstaniš povexave, ki ne ležijo na kratkih ciklih je dobra. Bi ga moral pa malo bolj podrobno pogledat. Bi se jo dalo uoprabit tudi drugje.
Vlado, mislim, da si tudi ti gledal trikotnike. To bi prišlo prav tudi pri soavtorstvih, oz. določevanju raziskovalnih skupin.
Vlado, 9.6.:
Ja, z Završnikom sva se ukvarjala s povezanostjo s kratkimi cikli / obroči članek. Stvar je za obroče dolžine 3 in 4 podprta v Pajku.
Tomo, 9.6.:
Vlado, to je zelo zanimivo. Jaz sem pa razmišljal o utežeh na povezavah. Povezava e ima utež, npr f(k), kjer je k dolžina najkrajšega cikla, ki gre skozi e, f pa je primerna funkcija, npr. 1/(1+k) ali kaj bolj primernega. V dobljenem omrežju se potem lahko greš otoke, pathfinder, …
Vlado, 9.6.:
V Pajku lahko za vsako povezavo dobiš kot utež število obročev dolžine 3 ali 4 (izbrane vrste v usmerjenih omrežjih). Kot uteženo stopnjo (vsota uteži povezav s krajiščem v danem vozlišču) dobimo vozliščno mero - število obročev izbrane vrste, ki gredo skozi dano vozlišče. Seveda so možne tudi razne transformacije. Za večje dolžine 5, 6, … postane izračun uteži časovno zahteven. Najbrž bi bilo dobro dodati dolžino 5. Za štetje lahko uporabimo tudi množenje (matrik) omrežja. Namesto obročev lahko v definiciji povezanosti uporabimo tudi kake druge majhne podgrafe - madžarski fiziki so uporabili klike.
Tomo, 10.6.:
Ja, če bi upošteval še število (najkrajših) obročev skozi vozlišče ali povezavo bi bile uteži bolj fino postavljene. Je pa preštevanje obročev časovno bolj zahtevno kot ugotavljanje najkrajše dolžie.
PS: Obroč je dobro poimenovanje cikla. Se pa bojim, da mi bo šlo pri mojih letih bolj težko v glavo.
Vlado, 10.6.:
Očiten algoritem za določanje dolžine najkrajšega cikla za vsako povezavo:
je kar zahteven m O(m+ n log n) - torej tudi za redka omrežja O(n^2 log n). Malo sem razmišljal, a kake bližnjice ne vidim. Pri realnih večjih omrežjih lahko včasih problem reduciramo, tako da najprej določimo razbitje na 2-povezane komponente, O(m), in uteži določamo po posameznih komponentah.
Izraz obroč oporabljam za semi-cycle (sklenjena veriga) v usmerjenih grafih.
PS.
Najbrž bi se dalo razmeroma učinkoviti določiti uteži, če bi postavili nek prag za “kratke” cikle (npr. 6 ali 10). Vsem povezavam, ki niso na kakem kratkem ciklu, pa bi pripisali isto utež - npr. prag+1.
Zgleda, da se da algoritem nekoliko pospešiti, tako da upoštevamo, kar smo med izvajanjem že izvedeli. Povezave so lahko v dveh stanjih: pregledane in nepregledane in imajo za vrednost dolžino trenutno najkrajšega cikla, ki gre skoznje. Pregledane povezave imajo pravo dolžino. Pri pregledovanju še ne pregledane povezave lahko uporabimo omejen Dijkstrov postopek, ki išče cikel dolžine največ trenutna dolžina - 1. Kadar pri pregledovanju najdemo cikel, popravimo trenutne dolžine na njem. Vsekakor je potrebno najprej narediti razbitje na dvopovezane komponente. Sicer grafi, ki so skoraj drevesa, zahtevajo veliko dela.
Tomo, 11.6.:
Ja, to bi bil zelo zanimiv postopek.
Mogoče bi pa lahko realizirali tudi ta postopek: Za graf G, ki je močno povezan, pa bi veljalo najprej poiskati vse pevezave, ,ki ležijo na trikotnikih. Naj bo dobljeni podgraf H3. Za triangulacije je to že konec, sicer bi za preostle povezave zaporedoma iskal daljše cikle, dolžine 4,5,… Lahko bi graf H3 razbil na povezane komponente. To je v bistvu najbolj fino razbitje omrežja, če odstranjuješ povezave, ki ležijo na daljših ciklih. Potem pa bi pregledoval zaporedoma samo povezave med različnimi povezanimi komponentami grafa H3, ali ležijo na štiriciklih. Z zlivanjem povezanih komponet bi dobil graf H4. Tako bi nadaljeval naprej, da dobiš H5, H6, …
Prednost tega postopka je, da ni potrebno gledat povezav znotraj posamezne komponente. (Upam, da ne odkrivam tople vode.)
Vlado, 11.6.:
Obtežitev trikotnikov, kot predfaza, je zelo dobra ideja. Zahtevnost je O(m). V večini realnih omrežij je trikotnikov zelo veliko. Tako, da se precej zmanjša množica povezav, na katerih je potrebno uporabiti Dijkstro oziroma bolje kar dvostrano iskanje v širino.
>>> wdir = "C:/Users/batagelj/work/Python/graph/Nets/paths" >>> os.chdir(wdir) >>> ====== RESTART: C:/Users/batagelj/work/Python/graph/Nets/paths/biBFS.py