Data for examples, libraries Nets and TQ
The TQ cores algorithm was presented at the Applied Statistics Conference 2016 in Ribno, Slovenia. In March 2019, I noticed that the TQ p_S algorithm is sensitive to rounding errors
>>> 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 == 1 False
I tried to account for this by introducing a tolerance eps into the algorithm. Setting eps = 0 we get the original 2016 version. I also added the function rounD(n, decimals=0) for pretty printing the results.
gdir = 'c:/users/batagelj/work/python/graph/Nets'
wdir = 'c:/users/batagelj/work/python/graph/Nets/bib'
# wdir = "C:/Users/batagelj/work/Python/graph/Nets/coresTQ"
# wdir = 'c:/users/batagelj/work/python/graph/JSON/SN5'
import sys, os, json
sys.path = [gdir]+sys.path; os.chdir(wdir)
from Nets import Network as N
from TQ import *
from datetime import datetime
eps = 1e-5
fJSON = 'CcNewman.json'
# fJSON = 'TerrorNews50.json'
def rounD(n, decimals=0):
multiplier = 10 ** decimals
return round(n * multiplier) / multiplier
def TQcorePs(G):
Tmin,Tmax = G._info['time']
D = { u: G.TQnetSum(u) for u in G._nodes }
Core = { u: [d for d in D[u] if d[2]==0] for u in G.nodes() }
D = { u: [d for d in D[u] if d[2]>0] for u in G.nodes() }
D = { u: d for u,d in D.items() if d!=[] }
Dmin = { u: min([e[2] for e in d]) for u,d in D.items() }
step = 0
while len(D)>0:
step += 1
dmin,u = min( (v,k) for k,v in Dmin.items() )
if step % 100 == 1:
print("{0:3d}. dmin={1:10.4f} node={2:4d}".format(step,dmin,u))
cCore = TQ.complement(Core[u],Tmin,Tmax+1)
core = TQ.extract(cCore,[d for d in D[u] if d[2] <= dmin+eps])
if core!=[]:
Core[u] = TQ.sum(Core[u],core)
D[u] = TQ.cutGE(TQ.sum(D[u],TQ.minus(core)),dmin)
for link in G.star(u):
v = G.twin(u,link)
if not(v in D): continue
chLink = TQ.minus(TQ.extract(core,G.getLink(link,'tq')))
if chLink==[]: continue
diff = TQ.cutGE(TQ.sum(D[v],chLink),0-eps)
D[v] = [ (sd,fd,max(vd,dmin)) for sd,fd,vd in diff ]
if len(D[v])==0: del D[v]; del Dmin[v]
else: Dmin[v] = min([e[2] for e in D[v]])
if len(D[u])==0: del D[u]; del Dmin[u]
else: Dmin[u] = min([e[2] for e in D[u]])
print("{0:3d}. dmin={1:10.4f} node={2:4d}".format(step,dmin,u))
return(Core)
G = N.loadNetsJSON(fJSON); G.delLoops(); G.Info()
print("Temporal Ps cores in: ",fJSON)
t1 = datetime.now(); print("started: ",t1.ctime(),"\n")
Core = TQcorePs(G)
t2 = datetime.now(); print("\nfinished: ",t2.ctime(),"\ntime used: ", t2-t1)
C4 = TQ.TQdictCut(Core,4-eps)
CR = { k : TQ.standard([ (s,f,rounD(v,3)) for (s,f,v) in C4[k] ]) for k in C4 }
for v in CR: print("{0:5d} : {1:11s} ".format(v,G.getNode(v,'lab')),CR[v])
>>>
=== RESTART: C:\Users\batagelj\work\Python\graph\Nets\coresTQ\PsCoresTQ.py ===
network: Network
Newman NORM of worksXauthors-year cumulative
simple= True directed= False org= 1 mode= 1 multirel= False temporal= True
nodes= 12458 links= 26261 arcs= 0 edges= 26261
Tmin= 1970 Tmax= 2008
Temporal Ps cores in: CcNewman.json
started: Thu Jul 9 02:38:47 2020
1. dmin= 0.0417 node= 548
101. dmin= 0.0488 node=5079
201. dmin= 0.1333 node=9918
...
13901. dmin= 1.7000 node=1377
14001. dmin= 2.0000 node=10540
14101. dmin= 2.0000 node=1946
14201. dmin= 2.0000 node=7043
14301. dmin= 2.1667 node= 394
14401. dmin= 2.5000 node= 634
14501. dmin= 3.0000 node=2232
14601. dmin= 3.5000 node= 69
14701. dmin= 5.3333 node=2232
14751. dmin= 19.1667 node=3169
finished: Thu Jul 9 02:39:05 2020
time used: 0:00:17.953027
20 : BORGATTI_S [(1990, 1991, 5.0), (1991, 1992, 6.0), (1992, 1993, 8.0), (1993, 1994, 10.0),
(1994, 1996, 12.0), (1996, 1997, 13.0), (1997, 1999, 14.0), (1999, 2003, 17.0),
(2003, 2005, 17.167), (2005, 2006, 18.167), (2006, 2009, 19.167)]
69 : WASSERMA_S [(2004, 2005, 4.0), (2005, 2006, 4.333), (2006, 2007, 4.833), (2007, 2009, 5.1)]
75 : HOLLAND_P [(1973, 1981, 4.0), (1981, 1983, 6.0), (1983, 2009, 6.333)]
78 : LEINHARD_S [(1978, 1981, 4.0), (1981, 1983, 6.0), (1983, 2009, 6.333)]
79 : NEWMAN_M [(2004, 2005, 4.0), (2005, 2009, 6.0)]
133 : BARABASI_A [(2002, 2009, 4.333)]
224 : SUITOR_J [(2000, 2009, 4.333)]
241 : WELLMAN_B [(2001, 2009, 4.167)]
258 : ALBERT_R [(2002, 2009, 4.333)]
317 : BERNARD_H [(1982, 1987, 5.0), (1987, 1990, 5.333), (1990, 1991, 5.5), (1991, 1995, 5.667),
(1995, 1997, 5.867), (1997, 1998, 5.967), (1998, 2001, 6.167), (2001, 2003, 6.267),
(2003, 2006, 6.333), (2006, 2009, 6.833)]
401 : HAWKINS_J [(1987, 2009, 4.0)]
428 : FRASER_M [(1987, 2009, 4.0)]
796 : PARK_J [(2004, 2005, 4.0), (2005, 2009, 6.0)]
925 : BONACICH_P [(1995, 1997, 4.333), (1997, 2009, 6.333)]
936 : GRABOWSK_A [(2006, 2009, 5.0)]
949 : BATAGELJ_V [(1994, 1995, 4.0), (1995, 2007, 5.0), (2007, 2009, 5.1)]
1056 : FAUST_K [(2004, 2005, 4.0), (2005, 2006, 4.333), (2006, 2007, 4.833), (2007, 2009, 5.1)]
1124 : HAMPTON_K [(2001, 2009, 4.167)]
1164 : DOREIAN_P [(1995, 2007, 5.0), (2007, 2009, 5.1)]
1166 : HUMMON_N [(1995, 2007, 5.0), (2007, 2009, 5.1)]
1336 : ENNETT_S [(1996, 2006, 4.0), (2006, 2007, 4.048), (2007, 2009, 4.148)]
1365 : BAUMAN_K [(1996, 2006, 4.0), (2006, 2007, 4.048), (2007, 2009, 4.148)]
1673 : MCCARTY_C [(2006, 2009, 4.333)]
1677 : JOHNSEN_E [(2006, 2009, 4.333)]
1680 : PATTISON_P [(2004, 2005, 4.0), (2005, 2006, 4.333), (2006, 2007, 4.833), (2007, 2009, 5.1)]
1789 : HANSSON_L [(2007, 2009, 5.333)]
1792 : BJORKMAN_T [(2007, 2009, 5.333)]
1794 : COHEN_C [(1981, 2009, 4.0)]
2083 : ROBINS_G [(2004, 2005, 4.0), (2005, 2006, 4.333), (2006, 2007, 4.833), (2007, 2009, 5.1)]
2084 : SKVORETZ_J [(1996, 2004, 4.0), (2004, 2006, 4.333), (2006, 2007, 4.833), (2007, 2009, 5.1)]
2232 : KILLWORT_P [(1982, 1987, 5.0), (1987, 1990, 5.333), (1990, 1991, 5.5), (1991, 1995, 5.667),
(1995, 1997, 5.867), (1997, 1998, 5.967), (1998, 2001, 6.167), (2001, 2003, 6.267),
(2003, 2006, 6.333), (2006, 2009, 6.833)]
2248 : MASUDA_N [(2006, 2009, 4.833)]
2307 : PILLEMER_K [(2000, 2009, 4.333)]
2622 : CHOU_K [(2001, 2005, 4.0), (2005, 2009, 5.0)]
3026 : CHI_I [(2001, 2005, 4.0), (2005, 2009, 5.0)]
3125 : SHELLEY_G [(2006, 2009, 4.333)]
3169 : EVERETT_M [(1990, 1991, 5.0), (1991, 1992, 6.0), (1992, 1993, 8.0), (1993, 1994, 10.0),
(1994, 1996, 12.0), (1996, 1997, 13.0), (1997, 1999, 14.0), (1999, 2003, 17.0),
(2003, 2005, 17.167), (2005, 2006, 18.167), (2006, 2009, 19.167)]
3170 : FERLIGOJ_A [(1994, 1995, 4.0), (1995, 2007, 5.0), (2007, 2009, 5.1)]
3174 : MRVAR_A [(2002, 2009, 4.667)]
3225 : FARARO_T [(1995, 2007, 5.0), (2007, 2009, 5.1)]
3618 : KOSINSKI_R [(2006, 2009, 5.0)]
3693 : SOKOLOVS_J [(1981, 2009, 4.0)]
3840 : BIENENST_E [(1995, 1997, 4.333), (1997, 2009, 6.333)]
4551 : STEINHAU_H [(2001, 2002, 4.0), (2002, 2003, 5.0), (2003, 2005, 6.0), (2005, 2006, 6.333),
(2006, 2009, 7.0)]
4860 : METZKE_C [(2001, 2002, 4.0), (2002, 2003, 5.0), (2003, 2005, 6.0), (2005, 2006, 6.333),
(2006, 2009, 7.0)]
5240 : KONNO_N [(2006, 2009, 4.833)]
12232 : LEINHARD_ [(1973, 2009, 4.0)]
>>>