**Who’s who in a network?**

The role a given vertice plays in the cohesiveness of the
network (its ‘importance’ or ‘centrality’ )can be assessed by a number of
social network metrics.

**Degree Centrality**is simply the number of connections (or edges) a vertex has to other vertices. Its clear from counting that #1’s degree centrality is 3, while vertex #4 has a measure of degree centrality equal to 1.

In terms of matrix algebra, if we can obtain this result as
a vector (one entry per vertice) as follows:

**x**= (1,1,1,1) degree =

**A’x**

**Eigenvector Centrality**is a measure that reflects the fact that not all connections are equal, and in fact, connections to people that are more influential are more important (Newman, 2012). Mathematically, the measure of eigenvector centrality is derived from the weights that consist of the values from the leading eigenvector (the eigenvector associated with the largest eigenvalue) of the adjacency matrix depicting the network.

Recall, the value

**λ**is an eigenvalue (or vector of eigenvalues) of the matrix**A**, and**x**is an eigenvector of**A**if the following equation holds:**λ x = A x**

So, for the network depicted above, the centrality measures
for each vertex = 1,2,3,4 can be derived from the components (x

_{1},x_{2},x_{3},x_{4}) that comprise the eigenvector**x,**and what we are interested in for this metric is the leading eigenvector (associated with the largest eigenvalue of A).
Eigenvectors and eigenvalues can be derived by solving:

**(A-λ I)x**= 0

This metric can be found using canned functions in SAS and
R. In SAS IML, the eigen function will allow you to obtain the leading
eigenvector

**x =**( 0.6116285,0.5227207,0.5227207,0.2818452).**A Path Centric Approach to Centrality**

One way of looking at centrality in terms of connectivity is
counting the number of paths emanating from a vertice to other vertices in the
network. For example, degree represents
the number of paths of length 1 to other vertices in the network. To look at this further, lets define the
matrix B as:

**B = A + I**, where I is the identity matrix of

**A**. The elements of

**B**represent the number of paths of length 1 from a vertice ‘i’ to another vertice ‘j’. The row sums of B tell us the total number of paths of length one emanating for a given vertice (counting each vertice itself as 1). We can store this sum for each vertice in a vector ‘

**d**’ obtained by multiplyting

**B’x**.

This gives us

**B’x**=**d1**= (4,3,3,2)
Now let’s define the matrix power of such that

**B**.^{2}= B*B
Each entry in B

^{2}represents the number of paths of length 2 from vertice i to vertice j.
The sum

**d2**=**B**=^{2}*x**d2**= (12,10,10,6) is the total number of paths of length 2 originating from each corresponding vertice.
So

**B**is a matrix with elements indicating the number of paths of length k between vertices i and j. The product^{k}**B**gives the sum of all paths of length k emanating from a given vertice. What we find is that as we consider longer and longer paths (as k becomes large) the normalized vector:^{k}*x**v = B**will approach the leading eigenvector of

^{k}*x / || B^{k}*x||**B**(which consequently is also the leading eigenvector of

**A**)

**v1 =**

**B**= (0.6488857,0.4866643,0.4866643,0.3244428)

^{1}*x / || B^{k}*x||**v5 = B**= (0.6121647,0.521951, 0.521951,0.2835289)

^{5}*x / || B^{k}*x||**v10 = B**=( 0.6116348,0.5227115,0.5227115,0.2818657)

^{10}*x / || B^{k}*x||
Recall the leading eigenvector of A:

x = ( 0.6116285,0.5227207,0.5227207,0.2818452)

So, what we have is a notion of eigenvector centrality as a
metric that captures the number of paths emanating from a given vertice. A
vertice that is connected to other vertices that also have lots of connections
will have a greater number of k-length paths originating from it. This is
information is reflected by eigenvector centrality. It turns out that the
iterative calculation of

**v**above is essentially the power iteration algorithm for calculating the leading eigenvector of a matrix**B**.
The following code from SAS IML and output provides an
illustration of the preceding discussion. In addition I have provided the function
written by Rick Wicklin that implements the power iteration algorithm used to
obtain the leading eigenvector and eigenvalue of a given matrix A.

**REFERENCES:**

Justification and Application of Eigenvector Centrality by
Leo Spizzirri https://www.math.washington.edu/~morrow/336_11/papers/leo.pdf

The power method: compute only the largest eigenvalue of
a matrix. The Do Loop. By Rick Wicklin.

**SAS IML MATRIX PROGRAMMING:**

**proc**

**iml**;

*specify adjacency matrix A;

A = {

**0****1****1****1**,**1**

**0**

**1**

**0**,

**1**

**1**

**0**

**0**,

**1**

**0**

**0**

**0**};

x = {

**1**,**1**,**1**,**1**};
* Degree centraltiy;

d1 = A*x;

print(A);

print(x);

print(d1);

call eigen(u,v,A);

print v;

B = A + I(

**4**);
print B;

d1 = B*x;

print d1;

B2 = B**

**2**;
print B2;

* Degree Centrality including
stopovers;

d1 = B*x;

print(d1);

d2 = (B**

**2**)*x;
print(d2);

d3 = (B**

**3**)*x;
print(d3);

* as k--> infinity, the
normalized vector v approaches the leading eigenvector of A and/or B;

v1 = d1/sqrt(d1[##]);

print v1;

d5 = (B**

**5**)*x;
print(d5);

v5 = d5/sqrt(d5[##]);

print v5;

d10 = (B**

**10**)*x;
print(d5);

v10 = d10/sqrt(d10[##]);

print v10;

**run**;

**quit**;

* Rick Wicklin's Power Method
Function;

**proc**

**iml**;

start PowerMethod(v,
A, maxIters);

/* specify relative tolerance used for convergence */

tolerance =

**1e-6**;
v = v / sqrt( v[##] ); /* normalize */

iteration =

**0**; lambdaOld =**0**;
do while ( iteration <= maxIters);

z = A*v; /* transform */

v = z / sqrt( z[##] ); /* normalize */

lambda = v` * z;

iteration = iteration +

**1**;
if abs((lambda - lambdaOld)/lambda) < tolerance then

return ( lambda );

lambdaOld = lambda;

end;

return (

**.**); /* no convergence */
finish;

* try our data;

A = {

**0****1****1****1**,**1**

**0**

**1**

**0**,

**1**

**1**

**0**

**0**,

**1**

**0**

**0**

**0**};

v = {

**1**,**1**,**1**,**1**};
lambda = PowerMethod(v, A,

**40**);
print lambda;

print v;

**run**;

**quit**;

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.