Luc Brun – Graph Edit Distance: Basics and History

Defining a metric between objects is a basic step of any pattern recognition algorithm. Using graphs, this notion of distance is not straightforward. Among the different distances between graphs that one may imagine, the Graph Edit Distance has progressively become a standard tool within the structural pattern recognition framework. Indeed, this distance allows to take into account fine differences between graphs, may be easily tuned and may satisfy all the axioms of a distance. Basically, the most common definition of the graph edit distance is based on the notion of edit path. An edit path between two graphs G1 and G2 is a sequence of node/edge removal/substitution or insertion operations transforming G1 into G2. Each edit path may be associated to a cost hence defining the Graph Edit Distance between G1 and G2 as the minimal cost of all edit paths between these two graphs. Within this survey, we will rst review some denitions and properties of the Graph Edit Distance in order to set up a framework which will allow us to review the main families of methods used to compute the graph edit distance. Among them, we may cite methods based on a tree search or methods based on integer programming.

Vladimir Batagelj: 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 [2]. 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 [3] and others. For details see [1].

[1] Batagelj, V., Doreian,P., Ferligoj, A., Kejˇzar, N. (2014). Understanding Large Temporal Networks and Spatial Networks: Exploration, Pattern Searching, Visualization and Network Evolution. Wiley Series in Computational and Quantitative Social Science. Wiley.
[2] De Nooy, W., Mrvar, A., Batagelj, V. (2011), Exploratory Social Network Analysis with Pajek; Revised and Expanded Second Edition. Structural Analysis in the Social Sciences, Cambridge University Press
[3] Doreian, P., Batagelj, V., Ferligoj, A. (2004). Generalized Blockmodeling. Structural Analysis in the Social Sciences. Cambridge University Press.