Basic Network Properties and How to Calculate Them • Data input • Number of nodes • Number of edges • Symmetry • Degree sequence • Average nodal degree • Degree distribution • Clustering coefficient • Average hop distance (simplified average distance) • Connectedness • Finding and characterizing connected clusters 2/16/2011 Network properties © Daniel E Whitney 1997-2006 1Matlab Preliminaries • In Matlab everything is an array •So – a = [ 2 5 28 777] – for i = a – do something –end • Will “do something” for i = the values in array a • [a;b;c] yields a column containing a b c • [a b c] yields a row containing a b c 2/16/2011 Network properties © Daniel E Whitney 1997-2006 2Matrix Representation of Networks »A=[0 1 0 1;1 0 1 1;0 1 0 0;1 1 0 0]1 2 A = 0 1 0 1 1 0 1 1 3 4 0 1 0 0 1 1 0 0 » A is called the adjacency matrix A(i, j) = 1 if there is an arc from i to j A( j,i) = 1 if there is also an arc from j to i In this case A is symmetric and the graph is undirected 2/16/2011 Network properties © Daniel E Whitney 1997-2006 3Directed, Undirected, Simple • Directed graphs have one-way arcs or links • Undirected graphs have two-way edges or links • Mixed graphs have some of each • Simple graphs have no multiple links between nodes and no self-loops 2/16/2011 Network properties © Daniel E Whitney 1997-2006 4Basic Facts About Undirected Graphs • Let n be the number of nodes and m be the number of edges •Then average nodal degree is < k >= 2m /n •The Degree sequence is a list of the nodes and their respective degrees n • The sum of these degrees is ∑di = 2m • D=sum(A) in Matlab i=1 D = [3 111] • sum(sum(A)) = 2m • Valid degree sequences add to an even number 2/16/2011 Network properties © Daniel E Whitney 1997-2006 5More Definitions and Calculations • Geodesic - shortest path between two nodes • Average path length = avg of all geodesics • Graph diameter = longest geodesic 2/16/2011 Network properties © Daniel E Whitney 1997-2006 6Data Input • Edge list: each row is an arc, the numbers of the nodes it connects are in columns 1 and 2, with the first node beingthe source and the second being the destination of the arc –Ni,Nj – Nk,Nl – An edge = 2 arcs, one in each direction, requiring two entries; often only one arc is listed so you have to knowif the matrix is intended to be symmetric or not • Node list: Node #1 in column 1, the node numbers of nodes it links to by outgoing edges in the next columns, however many are necessary – N1,Ni,Nj,Nk – N2,Nl,Nm • The easy way to generate these is to use Excel, save as “.csv” and load into Matlab using dlmread(‘filename.csv’); 2/16/2011 Network properties © Daniel E Whitney 1997-2006 7Example Node and Edge Lists Part of a nodelist. It is symmetric. 1 2 1 8 1 43 1 49 1 50 Part of an edgelist. 1 51 1 52 It is intended to be 1 53 1 54 symmetric but each 1 55 2 3 edge appears only once 2 9 2 44 so you have to make the 2 56 3 4 resulting matrix symmetric 3 10 3 45 yourself! 3 57 3 58 4 5 4 11 4 46 4 59 4 60 2/16/2011 Network properties © Daniel E Whitney 1997-2006 8Matlab Data Formats • Comma delimited, space delimited, tab delimited – All can be read using dlmread and written using dlmwrite • Lotus 1-2-3 format wk1 can be exchanged between Excel, Matlab, and UCINET – Matlab uses wk1read and wk1write – UCINET uses excel matrix input or small matrices can be pasted into UCINET’s matrix – Matlab also uses xlsread and xlswrite if you don’t need UCINET compatibility 2/16/2011 Network properties © Daniel E Whitney 1997-2006 9Data Input and Misc Ops • adjbuilde builds adjacency matrix from edge list • adjbuildn builds adjacency matrix from node list • diagnoseMatrix tests for power law • Miscellaneous data conversion – adj2str adjacency matrix to Matlab data structure – adj2pajek for input to Pajek graph software – adj2inc adjacency matrix to incidence matrix – str2adj reverses adj2str 2/16/2011 Network properties © Daniel E Whitney 1997-2006 10More Matlab Preliminaries • Logical expressions: • B=A > 1 returns a matrix B with entries = 1 everywhere matrix A has an entry > 1 • B is a logical matrix and can’t be operated on like numerical matrices can (can’t multiply, invert, etc) • B=B+0 converts B to a numerical matrix • Unitize(A) makes all non-zero entries in B = 1 – function unitize=unitize(A) – % unitizes a matrix, makes all non zero entries = 1 – unitize=A>0; – unitize=unitize+0; 2/16/2011 Network properties © Daniel E Whitney 1997-2006 11Still More Matlab Preliminaries • A’ = the transpose of A • sum(A) adds up each column and stores the result as a row vector • sum(A’) adds up each row and stores the result as a row vector • sum(sum(A)) adds up all the entries in A • length(x) counts the number of entries in vector x • find(x logical expr) returns the subscripts of entries in x that satisfy the logical expression using linear indexing – Linear indexing gives every entry one subscript • length(find(x logical expr)) tells how many entries in x satisfy the logical expression • [i,j]= find(x logical expr) returns the i and j subscripts of entries in matrix x that satisfy the logical expression 2/16/2011 Network properties © Daniel E Whitney 1997-2006 12More Preliminaries • idx=[a b c] • B=A(idx,idx) • B(i,j)=A(one of the combinations of a,b,c in pairs) – A = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 – idx = [1 2 5] – B= 1 2 5 6 7 10 21 22 25 2/16/2011 Network properties © Daniel E Whitney 1997-2006 13Number of nodes • Normally this is just the size of the network measured by the number of rows in the adjacency matrix: size(A,1) in Matlab –function numnodes=numnodes(A) – %finds number of nodes in A including isolates – numnodes=size(A,1); • But if there are isolated nodes, it’s useful to count only the non-isolated ones • So numnonisonodes works differently – function nodes = numnonisonodes(A) – % counts non-isolated nodes in a matrix – A=unitize(A+A'); – nodes=min(length(find(sum(A')~=0)),length(find(sum(A)~=0))); 2/16/2011 Network properties © Daniel E Whitney 1997-2006 14Number of Links or Edges • If A is symmetric (the network
View Full Document
Unlocking...