Approaches to Analysis of Large Networks

摘要

Large networks are networks with some thousands up to billions of nodes that can be entirely stored in computer's memory. Most of large networks are sparse - their number of links is of the same order as their number of nodes (Dunbar's number). This allows us to develop very efficient (subquadratic) algorithms for analysis of large networks. To support the analysis of large networks we started in 1996 to develop a program Pajek (De Nooy et al. 2011). Besides basic graph theory algorithms, such as weak and strong connectivity, condensation, topological ordering, etc., Pajek contains also several specific network analysis algorithms: 3-rings and 4-rings weights, SPC weights, (generalized) cores, fragment (motif) searching, network multiplication, cuts, islands, clustering and blockmodeling (Doreian et al. 2004) and others. For details see Batagelj et al. (2014).