ERGM parameter estimation of very large directed networks: implementation, example, and application to the geography of knowledge spillovers

ERGM parameter estimation of very large directed networks: implementation, example, and application to the geography of knowledge spillovers Alex Stivala 1 Alfons Palangkaraya 2 Dean Lusher 2 Garry Robins 3,2 Alessandro Lomi 1,4 1Universit`a della Svizzera italiana, Lugano, Switzerland. 2Swinburne University of Technology, Melbourne, Australia. 3The University of Melbourne, Melbourne, Australia. 4University of Exeter Business School. INSNA Sunbelt XXXIX, Montr´eal, Canada, June 18–23, 2019 1 / 27 Introduction IEstimation of two very large (over 1 million nodes) directed networks: IAn online social network with approx. 1.6 million nodes. IA patent citation network with approx. 3.8 million nodes. IUsing a new implementation of the EE algorithm (Byshkin et al., 2018) for directed networks, Iand also implemented so that very large networks can be handled (earlier implementations run into limits of memory usage and data structure efficiency). IA substantive contribution in examining geographical knowledge spillover effects using the patent citation network. 2 / 27 Previous work with on large network ERGM estimation IStivala et al. (2016) Soc. Netw. 47:167–188 estimate ERGM parameters from snowball samples (undirected networks only). IStivala et al. (2015) Sunbelt XXXV Brighton [unpublished manuscript] extension of snowball sampling method to directed networks. IByshkin et al. (2016) J. Stat. Phys. 165:740–754 introduced the IFD sampler which increases the ESS by an order of magnitude with corresponding decrease in estimation time. IByshkin et al. (2018) Sci. Rep. 8:11509 introduced the Equilibrium Expectation (EE) algorithm which is shown to be two orders of magnitude faster than existing methods, and applied to a 104 103 node social network (Livemocha) and several smaller biological networks. 3 / 27 Extension to directed networks IIFD and EE were initially only implemented for undirected networks. IThe EE algorithm was extended to directed networks and reimplemented (only using the “basic” sampler, not IFD yet) and applied to some directed networks: IThe 1490 node political blogs network (Stivala et al. (2018), unpublished) IA 3308 node hospital transfer network (Stivala et al. (2018) INSNA Sunbelt XXXVIII (Utrecht) [unpublished manuscript]). ITwo biological networks with 423 and 1781 nodes (Stivala et al. (2018) PASC 2018 Basel poster presentation [unpublished manuscript]. IThe IFD sampler is now also implemented for directed networks and applied in the EE algorithm to the very large directed networks described here. 4 / 27 Pokec IPokec is the most popular online social network in Slovakia. IThe network data (Takac & Zabovsky, 2012) is the entire anonymized network containing various attributes such as gender, age, region (187, in Slovakia or elsewhere), etc. I“Friendships” in Pokec are directed (and not necessarily reciprocated). IThe network has 1 632 803 nodes and 30 622 564 arcs. IThe network is described as “scale-free” by Takac & Zabovsky (2012), but only based on eyeballing a degree–frequency plot. 5 / 27 Patent citations IThe NBER patent citation network (Hall, Jaffe, & Trajtenberg, 2001). ICitation network of patents granted between 1975 and 1999. IThere are 3 774 768 nodes and 16 518 948 arcs (citations). IThere is data about the patents (category, subcategory, application date, inventor location, etc.) for patents from 1963 to 1999. IThere is such data for 2 755 865 patents in the citation network II.e. approx. 73% of the patents in the citation network have attribute data. IThere are 6 patent categories and 36 subcategories (derived from the original 400 classes from USPTO). 6 / 27 Graph summary statistics Description N Components Mean Density Clustering Assortativity degree coefficient coefficient Pokec 1632803 1 37.51 0.000011 0.04682 -0.00049 Pokec (no hubs) 1632783 577 37.38 0.000011 0.05369 0.07867 Patents 3774768 3627 8.75 0.000001 0.06714 0.13317 Patents (NA removed) 2755865 13401 10.14 0.000002 0.07193 0.13397 7 / 27 Previous work on the patent citation network, particularly relating to “knowledge spillovers” IReviewed in Jaffe & de Rassenfosse (2017). IJaffe, Trajtenberg, & Henderson (1993) using patent class matching between citing and “control” patents, find that citations are more likely to be geographically proximate, evidence for knowledge spillover effect. IThompson & Fox-Kean (2005) argue that using the patent class is too coarse and use a finer-grained matching, finding the spillover effect is then reduced at the intra-national level (but not the international level). IHenderson, Jaffe, & Trajtenberg (2005) respond that the question is how robust the localization effect is under different assumptions. IHowever note all of this (in common with most economics work using networks) treats the network as exogenous. Using ERGM the network is instead endogenous. 8 / 27 Pokec degree distribution 1 10 100 1000 10000 0.000001 0.000100 0.010000 1.000000 Pokec In−degree CDF Power law α = 5.079 Log−normal µ = 3.68 σ = 0.679 1 10 100 1000 10000 0.000001 0.000100 0.010000 1.000000 Pokec Out−degree CDF Power law α = 4.096 Log−normal µ = 3.222 σ = 0.816 Consistent with neither power law nor log-normal (p<0.01) 9 / 27 Pokec results interpretation [1] ICentralization on both inand outdegree. IPositive activity closure: people who send ties to the same people tend also to have a tie (however shared activity is also positive, so can we conclude this?) IPositive path closure: friends of friends also tend to be friends. IPositive cyclic closure (non-hierarchical network closure). Note this is quite rare in friendship networks (although this apparent rarity may be spurious (Block, 2015)). IHowever this apparent “generalized exchange” effect seems to be reduced when reciprocity is explicitly included in the model, and cyclic triads (030C) appear to have reasonable fit in the “pseudo-GoF” plots whether or not cyclic closure is included in the model with reciprocity included. I(Note however triad 021C [directed line] does not have great fit, despite A2P-T being included in the model; when Reciprocity is not included, 021C is too high, and when it is included, 021C fits better, but (slightly) too low.) 16 / 27 Pokec results interpretation [2] IThere is significant homophily on age and region. IWe don’t find any significant effects of profile completion percentage or profile “public” flag. IThere is significant heterophily on gender. (This seems interesting/unusual for a social network: is it being used for “dating”?) 17 / 27 Special properties of citation networks IThere are no reciprocated arcs (or nearly none; but there are exactly 0 in this data). ISo cannot include reciprocity in the model, and so a constraint is implemented in the sampler to prevent such arcs being created in the simulation. IThings “in the future” can’t be cited, i.e. a patent or publication can only cite one that is already published (or applied for) — although exceptions can also occur due to long review times, etc. IThis means that citation networks are (approximately) directed acyclic graphs. 18 / 27 The DiffSign parameter ITo account for this we introduced the “DiffSign” statistic on a continuous attribute a, which for an an arc i→jis +1 if ai>aj,−1 if ai<aj, and 0 if ai=aj ISo if the attribute is the patent date, the DiffSign parameter is significantly positive if patents tend to cite those in the past. IThis is similar to an ergm.userterm added to statnet for this purpose, described by Graham et al. at Utrecht Sunbelt (2018) and published as McLevey et al. (2018). INote we could also implement a constraint in the simulation to prevent this happening at all, but it can be preferable to do it this way as for example in this case the data does contain some patents that cite those “in the future”. 19 / 27 Estimating the patent citation network I8 parallel tasks with 55 GB each (default “slim” partition). IElapsed time approx. 2 hours. IIFD sampler acceptance rate approx. 28%. 20 / 27 Estimation results IFull citation graph (3 774 768 nodes) ISubgraph induced by nodes that have patent data (2 755 865 nodes). IFor the full graph, 45% of nodes are sinks (cite no other patents) and 14% of nodes are sources (are not cited). IWe include the Sink and Source parameters to control for this. IFor the subgraph only 26% of nodes are sinks and 19% are sources (many of the removed patents without attributes were sinks). INote base for sender year is 1975 but for receiver year is 1963 as citation data starts in 1975, but full patent attribute data starts in 1963 (see also “quasi-structural” model, Table 3 of Hall, Jaffe, & Trajtenberg, 2001). IAs will be seen on the next slide, results are not substantively different. 21 / 27 Effect Full graph Subgraph Arc −17.139 (−17.823,−16.456) −18.542 (−19.161,−17.922) Sink 3.876 (2.915,4.838) 1.735 (1.697,1.772) Source −0.867 (−0.890,−0.844) −0.762 (−0.782,−0.741) Popularity spread (AinS) 1.192 (0.985,1.399) 1.198 (0.939,1.457) Activity spread (AoutS) 0.395 (0.368,0.423) 0.427 (0.406,0.447) Two-path (A2P-T) −0.018 (−0.037,0.001) −0.015 (−0.035,0.006) Shared popularity (A2P-D) 0.022 (0.001,0.043) 0.018 (−0.001,0.037) Shared activity (A2P-U) 0.026 (0.007,0.045) 0.028 (0.005,0.050) Sender APPYEAR [1975] 0.019 (0.002,0.035) 0.046 (0.032,0.059) Receiver APPYEAR [1963] −0.050 (−0.064,−0.036) −0.044 (−0.059,−0.030) DiffSign APPYEAR 1.743 (1.520,1.966) 2.333 (1.913,2.752) Diff APPYEAR −0.105 (−0.120,−0.090) −0.101 (−0.116,−0.085) Sender CLAIMS 0.010 (−0.007,0.027) 0.014 (−0.000,0.028) Receiver CLAIMS 0.011 (−0.003,0.025) 0.010 (−0.004,0.024) Diff CLAIMS −0.005 (−0.018,0.009) −0.007 (−0.018,0.004) Matching CAT 0.799 (0.623,0.974) 1.025 (0.841,1.208) Matching SUBCAT 2.895 (2.222,3.568) 2.897 (2.205,3.589) Matching COUNTRY 0.222 (0.155,0.289) 0.457 (0.284,0.631) Matching POSTATE 0.830 (0.341,1.320) 0.842 (0.340,1.344) Matching ASSIGNEE 3.889 (1.414,6.363) 3.823 (1.578,6.068) 22 / 27 Patent citation estimation results IModels with triangles (closure) included did not converge well, even with far more iterations. IThere are always exactly 0 triads with reciprocity due to the constraint. IBut a very small number of cyclic triads (030C) are created in the simulated networks, even though there are exactly 0 in the observed network. IThere is centralization on in-degree and out-degree. IPositive shared activity, shared popularity, negative simple two-path. Models structure, but in absence of converged models with closure parameters, no real useful interpretation? 23 / 27 Patent citation results interpretation IPositive DiffSign parameter on application year: as expected, patents are more likely to cite those applied for earlier in time. IPositive sender and negative receiver on application year: more recent patents make more citations but receive fewer (control for fact that older patents have more time to get citations, and citation rates increase over time). ISignificant negative heterophily on application year: patents are more likely to cite patents closer in time (more recent). ISignificant homophily on category and subcategory. ISignificant homophily on assignee: “self-citation” indicating mostly internalized knowledge transfers. ISignificant homophily on country and state: The geographic spillover effect hypothesis is confirmed at both the country and state levels. (While also controlling for homophily on technology category and subcategory and assignee). 24 / 27 Conclusions / contributions IMethodological IFreely available code for ERGM estimation of very large directed networks using the recently published EE algorithm and IFD sampler. IDemonstration ERGM parameter estimation of the largest (online) social network for which an ERGM has ever been estimated to date (1.6 million nodes). IERGM parameter estimation of the largest network for which an ERGM has ever been estimated to date (over 3.7 million nodes). IThe latter is a special case as it is a citation network and so special constraints and parameters were also introduced. ISubstantive (patent citation network and spillover effects) IUsing more sophisticated statistical techniques to more closely examine claims about the degree distributions of the patent citation network, finding that only the in-degree distribution is consistent with a power law. ITreating the citation network as endogenous (not exogenous as in previous work) and finding the geographical spillover effect appears to be robust to this. 25 / 27 Pokec degree distribution (20 highest degree nodes removed) 1 5 10 50 100 500 1000 0.000001 0.000100 0.010000 1.000000 Pokec (hubs removed) In−degree CDF Power law α = 5.45 Log−normal µ = 3.76 σ = 0.654 1 5 10 50 100 500 1000 0.000001 0.000100 0.010000 1.000000 Pokec (hubs removed) Out−degree CDF Power law α = 4.134 Log−normal µ = 3.229 σ = 0.812 In-degree distribution is consistent with power law, but not log-normal (p<0.01). Out-degree distribution is consistent with neither power law nor log-normal (p<0.01). 5 / 27 Standard error estimation IFor each parallel MCMC run, the parameter and its standard error are estimated: IThe point estimate (mean) and asymptotic covariance matrix (batch means method) for MCMC standard error are estimated using the mcmcse R package (Flegal et al., 2017). IThe covariance matrix for the error in approximating the MLE is estimated as the inverse of the covariance matrix of the simulated statistics (Fisher information), also using mcmcse. IThe total estimated covariance matrix is then estimated as the sum of these two covariance matrices, and from this we compute the standard error. IThe overall estimate and its standard error are then estimated as the inverse variance weighted average of these parallel runs. 6 / 27 Technical details ICompletely new implementation of the EE algorithm and IFD sampler in C, using MPI to run multiple estimations in parallel. IEfficient data structures and algorithms so that computation of change statistics is fast and scalable: IGraphs stored as adjacency lists for memory efficiency, with both forward and reverse adjacency list for fast computation of change statistics, as well as flat list of all arcs for fast lookup of random arcs (needed by IFD sampler). IFor fast computation of the “alternating” statistics, three two-path tables are built. IIn PNet these are arrays but this is not scalable; so instead we take advantage of sparsity and use hash tables, with Bloom filter for fast misses. (Implemented in the “uthash” library https: //troydhanson.github.io/uthash/userguide.html) IFor good pseudorandom number generation, the Random123 counter-based PRNG (Salmon et al., 2011) is used. 7 / 27 More technical details IUsing hash tables and not arrays for two-path lookup tables is vital. IIt is also very advantageous to use a Bloom filter so that the overwhelmingly more frequent case of looking up an entry that is not present is faster. IDuring the MCMC process arcs are added and deleted, and it is also essential to delete from the hash tables any two-path values that fall to zero, to stop the tables growing indefinitely. (Unfortunately, however, this diminishes the effectiveness of the Bloom filter). IFor the Pokec network, these matrices are approx 0.06% nonzero, and so use approx. 200 GB instead of the nearly 10 TB they would occupy as arrays. IFor the patent citation network, they are approx. 0.001% nonzero, and so use approx. 10 GB instead of the 50 TB they would occupy as arrays. 8 / 27 Ongoing and future work and problems (methodological 1) IThe EE algorithm used here required “tuning” of hyper-parameters, but a new version was recently proposed which has only one hyper-parameter (Borisenko et al., 2019), potentially making it easier to obtain converged models. IThese were whole network estimations, but snowball sampling and conditional estimation are also implemented, to allow even larger networks via snowball samples. IAlso need to extend to bipartite (or more generally multilevel) networks. ISome empirical networks of interest have two-path matrices that are not sparse enough or have the “wrong” structure for either the efficient two-paths data structure or snowball sampling to work well with, e.g. the approx. 1 million node physician referral network described by An et al. (2017). Why? What to do about it? 9 / 27 Ongoing or future work and problems (methodological 2) IContrastive Divergence and the EE algorithm are fast as we “cheat” in the MCMC and do not need burn-in. ISo our “pseudo-GoF” we use as a check is probably over-optimistic. IBut we can’t practically simulate such large ERGM networks from scratch to do it properly. ISo we need some other way, for example by simulating snowball samples and comparing statistics to snowball samples from the observed network. IAlso, we know bias in the ERGM MLE for some parameters (in undirected case: Edge, Alt.K-Star) in these models gets worse for larger networks (Stivala, Byshkin, & Robins 2017 Sunbelt Beijing; unpublished manuscript). IDoes an ERGM even make sense for such large networks, especially the homogeneity assumption? 10 / 27 Future work and problems (substantive) IAs per Henderson, Jaffe, & Trajtenberg (2005), the question of what level of patent class /category / subcategory to match is not clear. IIn the matching techniques used by Jaffe, Trajtenberg, & Henderson (1993) and Thompson & Fox-Kean (2005) patents with the same assignee are excluded, Ibut instead we include a model term to control for this, in the framework of ERGM terms which are nested (matching country, matching state, matching assignee). IBut perhaps as a robustness check it should be run on data with patents with the same assignees excluded? IWe do not include a matching term for same inventor, however, and perhaps this should be done (Henderson, Jaffe, & Trajtenberg, 2005) IHowever this involves more “linking out” (data set matching). IMore importantly, perhaps patent citations do not even capture localization of knowledge transfers (“spillovers”) at all (Arora, Belenzon, & Lee, 2018). 11 / 27 Pokec (no hubs) parameter trace 12 / 27 Pokec (no hubs) convergence trace 13 / 27 Pokec (no hubs) pseudo-GoF (model 1) 0.00 0.04 0.08 0.12 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988 in−degree fraction of nodes 0.000 0.005 0.010 0.015 0.020 0 250 500 750 1000 in−degree density obs sim 0.0 0.2 0.4 0 2 4 6 log in−degree density obs sim 0.00 0.05 0.10 0.15 012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052 out−degree fraction of nodes 0.000 0.005 0.010 0.015 0 300 600 900 out−degree density obs sim 0.0 0.1 0.2 0.3 0.4 0246 log out−degree density obs sim ● 0.00 0.25 0.50 0.75 1.00 reciprocity fraction of arcs ● 0.00 0.25 0.50 0.75 1.00 giant component fraction of nodes ● ● 0.00 0.25 0.50 0.75 1.00 average local global clustering coefficient 0e+00 1e−10 2e−10 3e−10 4e−10 5e−10 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census fraction of triads 1e−12 1e−11 1e−10 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census frac. triads (log) 14 / 27 Patent convergence trace (subgraph) 21 / 27 Patent citation pseudo-GoF ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●● 0.00 0.05 0.10 0.15 0.20 0.25 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812 in−degree fraction of nodes 0.00 0.01 0.02 0.03 0 200 400 600 800 in−degree density obs sim 0.00 0.25 0.50 0.75 1.00 1.25 0 2 4 6 log in−degree density obs sim ● ● ● ● ● ● ● ● ● ● ● ●● ●●● ●● ●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●● ●●●●●●●●●●●●●●●●●●●●● 0.0 0.1 0.2 0.3 0.4 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796 out−degree fraction of nodes 0.00 0.01 0.02 0.03 0 200 400 600 800 out−degree density obs sim 0.00 0.25 0.50 0.75 0 2 4 6 log out−degree density obs sim ● 0.00 0.25 0.50 0.75 1.00 reciprocity fraction of arcs ● 0.00 0.25 0.50 0.75 1.00 giant component fraction of nodes ● ●● 0.00 0.25 0.50 0.75 1.00 average local global clustering coefficient ●● 0.0e+00 5.0e−12 1.0e−11 1.5e−11 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census fraction of triads ●● 1e−17 1e−15 1e−13 1e−11 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census frac. triads (log) 22 / 27 Patent citation (NA excluded subgraph) pseudo-GoF ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ●● ● ● ●●●●●● ● ●● ● ● ●● ●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●● 0.00 0.05 0.10 0.15 0.20 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817 in−degree fraction of nodes 0.00 0.01 0.02 0.03 0 200 400 600 800 in−degree density obs sim 0.0 0.2 0.4 0.6 0.8 0246 log in−degree density obs sim ● ● ● ● ● ● ● ● ● ● ● ● ●● ●● ● ●● ● ●●●●●●● ●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●● 0.0 0.1 0.2 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776 out−degree fraction of nodes 0.00 0.01 0.02 0.03 0 200 400 600 800 out−degree density obs sim 0.0 0.2 0.4 0.6 0 2 4 6 log out−degree density obs sim ● 0.00 0.25 0.50 0.75 1.00 reciprocity fraction of arcs ● 0.00 0.25 0.50 0.75 1.00 giant component fraction of nodes ● ●● 0.00 0.25 0.50 0.75 1.00 average local global clustering coefficient 0e+00 1e−11 2e−11 3e−11 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census fraction of triads 1e−17 1e−15 1e−13 1e−11 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C 210 300 Triad census frac. triads (log) 23 / 27 Validation on simulated network N= 2000 binary attributes −2 −1 0 Nc=100, bias =0.2118, RMSE =0.3077 % In CI =98, FNR% =67 Arc 3.9 4.1 4.3 4.5 Nc=100, bias =−0.1359, RMSE =0.1638 % In CI =63, FNR% =0 Reciprocity −2.5 −2.0 −1.5 Nc=100, bias =−0.01094, RMSE =0.09741 % In CI =100, FNR% =0 AinStar −2.5 −2.0 −1.5 −1.0 Nc=100, bias =−0.2228, RMSE =0.2395 % In CI =100, FNR% =0 AoutStar −0.5 0.0 0.5 1.0 Nc=100, bias =0.03165, RMSE =0.1335 % In CI =90, FNR% =3 AKT−T −0.5 −0.4 −0.3 −0.2 −0.1 0.0 0.1 Nc=100, bias =−0.02428, RMSE =0.04394 % In CI =100, FNR% =69 A2P−TD 0.50 0.75 1.00 1.25 1.50 Nc=100, bias =−0.03484, RMSE =0.1083 % In CI =97, FNR% =0 Receiver 1.00 1.25 1.50 Nc=100, bias =−0.247, RMSE =0.2617 % In CI =16, FNR% =0 Sender 1.5 1.8 2.1 Nc=100, bias =−0.135, RMSE =0.1915 % In CI =50, FNR% =0 Interaction 24 / 27 Validation on simulated network N= 2000 categorical attributes −2 −1 0 1 Nc=100, bias =0.5514, RMSE =0.612 % In CI =85, FNR% =100 Arc 1 2 3 4 5 Nc=100, bias =−0.06365, RMSE =0.2745 % In CI =100, FNR% =0 Reciprocity −3.0 −2.5 −2.0 −1.5 −1.0 Nc=100, bias =0.006004, RMSE =0.1298 % In CI =100, FNR% =0 AinStar −3.0 −2.5 −2.0 −1.5 −1.0 Nc=100, bias =−0.4346, RMSE =0.4506 % In CI =98, FNR% =0 AoutStar 0.95 1.00 1.05 1.10 Nc=100, bias =0.01574, RMSE =0.02084 % In CI =100, FNR% =0 AKT−T −0.4 −0.3 −0.2 −0.1 0.0 0.1 Nc=100, bias =−0.02848, RMSE =0.04114 % In CI =100, FNR% =40 A2P−TD 1.3 1.4 1.5 1.6 1.7 Nc=100, bias =−0.005768, RMSE =0.03965 % In CI =100, FNR% =0 Matching 1 2 3 4 5 Nc=100, bias =0.09297, RMSE =0.2901 % In CI =100, FNR% =0 Matching reciprocity 25 / 27 Type I error rate validation N= 2000 node simulated networks N Attr. Effect Bias RMSE False positive rate (%) in C.I. Total Mean Total Estim. 95% C.I. (%) networks runs runs per lower upper converged converged network 2000 Cat. A2P-TD -0.0217 0.0657 1 0 5 99 100 31.94 32 2000 Cat. AinS -0.0017 0.0648 1 0 5 99 100 32.00 32 2000 Cat. AKT-T -0.0154 0.0837 0 0 4 100 100 32.00 32 2000 Cat. AoutS -0.0129 0.0706 1 0 5 99 100 32.00 32 2000 Cat. Match.Recip. 0.1246 0.1981 9 5 16 91 100 32.00 32 2000 Cat. Reciprocity 0.4809 0.5493 2 1 7 98 100 30.86 32 2000 Bin. A2P-TD -0.0143 0.0198 2 1 7 98 100 32.00 32 2000 Bin. AinS -0.1234 0.1830 1 0 5 99 100 32.00 32 2000 Bin. AKT-T -0.2473 0.5563 1 0 5 99 100 29.32 32 2000 Bin. AoutS -0.0011 0.0954 0 0 4 100 100 32.00 32 2000 Bin. Interaction -0.7966 3.0590 4 1 15 96 46 7.02 32 2000 Bin. Receiver 0.0313 0.1577 5 2 11 95 100 31.33 32 2000 Bin. Reciprocity -0.3127 1.2360 0 0 14 100 24 6.96 32 2000 Bin. Sender 0.0244 0.1252 2 1 7 98 100 30.73 32 26 / 27 Institute of Computational Science (ICS) cluster details USI ICS cluster https://intranet.ics.usi.ch/HPC operating system CentOS 7.5 x86 64, OpenMPI slim (22 nodes) 2 x Intel Xeon E5-2650 v3 @ 2.30GHz, 20 (2 x 10) cores, 64 GB RAM fat (7 nodes) 2 x Intel Xeon E5-2650 v3 @ 2.30GHz, 20 (2 x 10) cores, 128 GB RAM bigMem (2 nodes) 2 x Intel Xeon E5-2650 v3 @ 2.30GHz, 20 (2 x 10) cores, 512 GB RAM 27 / 27