Layouts for GD01 graph-drawing competition.pdf

Layouts for GD01 Graph-Drawing Competition Vladimir Batagelj Faculty of Mathematics and Physics University of Ljubljana e-mail: vladimir.batagelj@uni-lj.si Andrej Mrvar Faculty of Social Sciences University of Ljubljana e-mail: andrej.mrvar@uni-lj.si September 15, 2001 1 How layouts of graphs were obtained All work was done using our program package Pajek, which is freely available at: http://vlado.fmf.uni-lj.si/pub/networks/pajek/ Graph A Citation networks analysis In a given set of units E (articles, books, works, . . . ) we introduce a citing relation R ? E × E xRy ≡ y cites x which determines a citation network (E, R). A citing relation is usually irreflexive, ?x ∈ E : ?xRx, and (almost) acyclic, ?x ∈ E ?k ∈ IN+ : ?xRkx. The citation network is standardized by adding, if necessary, artificial source vertex s and sink or terminal vertex t and the arc (t, s) (see figure). An approach to the analysis of citation network is to determine for each unit / arc its importance or weight. These values are used afterwards to determine the essential substructures in the network. Hummon and Doreian (1989, 1990) proposed three methods of assigning weights w : R → IR+0 to arcs: ? NPCC method: w1(u, v) = |R?1(u)| · |R(v)| ? Paths count method: w2(u, v) = N(u, v), where N(u, v) denotes the number of different paths from Min R to Max R (or from s to t) through the arc (u, v) ? SPLC method: w3(u, v) = N ′(u, v), where N ′(u, v) equals to N(u, v) from paths count method over the network (E, R′), R′ := (R ∪ {s})× (E \ {s, t}) The last two methods are efficiently (Batagelj, 1991, 1994) implemented in Pajek and can be applied also on (very) large acyclic networks. Let N?(v) denotes the number of different paths from s to v, and N+(v) denotes the number of different paths from v to t. Then N(u, v) = N?(u) · N+(v), (u, v) ∈ R. N and N ′ are flows in the network since they obey the Kirchoff’s node law: For every node v in a citation network (E, R) in standard form it holds incoming flow =