Skip to main content

Posts

Featured

Mathematical Proofs: How LinkedIn defines nth degree connections

Previously , i had shown the property of graphs used to identify nth degree connections. Here i show a proof of the same

An important point to note here is that if A*B=C and A,B,C are matrices , the C(ij) = ith row of A * jth column of B.

Hence , if adjacency Matrix of a graph is A, An  = A*A*A*....*A .If A is un-directed it is symmetric.

As in a previous post ,ij-th element of An is the number of links of length n from ith node to the jth node.

An  = A*A*A*....*A

Hence (ij)th element of A2 can be expressed as 

∑a(i,k)*a(k,j)where k = 1,2...,N ----(1)

Here, N=stands for total number of nodes (1 to N) , k any arbitrary node from 1 to N, i the ith node and j the jth node .

Let us now generalize the above expression for (ij)th element of An  as 

....∑ (a(i,k1)*a(k1,k2)*a(k2,k3)*a(k3,k4)*.....a(k(n-1),j)where k1,k2,k3,k4....k(n-1) each 
                                                                                                              = 1,2....,N ----(2)

rewriting (2) as ∑ ...a(k(n-…

Latest Posts

Mathematical Proofs: The Largest Eigenvalue of a Stochastic Matrix is 1

How LinkedIn identifies 1st,2nd,3rd degree connections

Taylor Series : ( A Simple Overview )

Agent-Based Simulation

Decision Making : a benchmark of AI capabilities

Genetic Algorithm