Blog Archive

Friday, July 24, 2015

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, A = A*A*A*....*A .If A is un-directed it is symmetric.

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

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

Hence (ij)th element of A
2   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 A 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-1),j)*...a(k3,k4)*a(k2,k3)* (a(i,k1)*a(k1,k2) 


the summation nested at the innermost , has already been shown in (1);solving it recursively for each nested summation using (1) itself we arrive at the number of links of length 'n' from for i-j.

yes , it is intuitive :)

Saturday, July 18, 2015

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

This result is very important in many graph-based problems like the PageRank algorithm;i thought it would be worthwhile posting a simple proof to the same

Lets assume the stochastic matrix to be A. For this calculation , it is assumed that it is row stochastic matrix;hence each row adds up to 1.
So A*1=1 .This consequentially shows that 1 is one of the eigenvalues

(Ax = λx)---- (1)

Now lets proceed to prove that an eigenvalue greater than 1 cannot exist.For this we assume that there does exist such a λ. However from the L.H.S of (1) , we see that each element of the result of the matrices product is an convex combination of the elements of x itself.Hence no element in the result vector can be greater than the largest of the elements of x.However if λ >1 , then λx is clearly going to have elements greater than the largest of x's elements.This contradiction sufficiently shows that the largest eigenvalue for a stochastic matrix has to be 1.

Saturday, July 11, 2015

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

LinkedIn identifies connections based on how close the user is to that profile.An easy way to understand this is to treat the entire network of users as a graph.

Key component of any graph is the adjacency matrix.It identifies the number of direct connections between any two nodes (read as users) in the graph.Say we have the following sample graph of 6 users .
 The set space here is the states of { 1,2,3,4,5,6}.Let us assume that these states are 6 users .Here, we have a directed graph (means the direction is specified).However, in case of LinkedIn, it is bi-directional( this only will change the adjacency matrix). The adjacency matrix for the above graph is as follows :

*Column (ij) marks the number of direct links from user(i) to user(j)
*In the graph , we assume there is no back-link from a node to itself , because as we will see below , it will mess up the process.

User-Node
1
2
3
4
5
6
1
0
1
0
0
0
0
2
0
0
0
0
0
0
3
0
1
0
1
0
0
4
0
0
0
0
0
0
5
0
0
1
0
0
1
6
0
0
0
0
0
0

Lets's call this adjacency matrix A. 

In order to figure out whether there is a nth degree connection between node (i) and node (j) .We have to figure out if there is a n-step link between node (i) to node (j) .

let n(ij) be the n-step links between ith and jth user

n(ij) = 'ij'th element of  An

For example :

If n=2 , n(ij) would give the number of possible paths of length 2 , from i to j.
the matrix would be as

User-Node
1
2
3
4
5
6
1
0
0
0
0
0
0
2
0
0
0
0
0
0
3
1
0
0
0
0
0
4
0
0
0
0
0
0
5
0
1
0
1
0
0
6
0
0
0
0
0
0

Note that there is a 2-step link between 5 &4 user , 5 & 2 user , 3 & 1 user.Hence for the 5th user , i could say it has the 4th and 2nd user as its 2nd degree connections.



this again, is how FACEBOOK recommends friends to you .

I'll post the mathematics behind the equivalence of nth power of A and n-step link between i and j node is my next post

Thursday, July 2, 2015

Taylor Series : ( A Simple Overview )

A Taylor Series is a mathematical representation of a function in terms of an infinitely extending sum of polynomial terms .The advantage is implicit in the definition.By extending a function as a sum of polynomials it becomes much easier to analyse the function and study interesting properties of it. In sigma notation :

 \sum_{n=0} ^ {\infty} \frac {f^{(n)}(a)}{n!} \, (x-a)^{n}   an infinitely extending power series


To fully appreciate how interesting Taylor Series are , it is important to know the interval of convergence . The interval is generally obtained using a ratio-test on the series itself. This helps us to realize the interval within which the Taylor Series , is accurate enough to be passed on as the representation of the function .

In fields varying from economics to civil engineering , it helps us to put out a finite order polynomial approximation to a function .This in turn helps in sufficient estimation of the function as required.There are several specific features/properties of Taylor series that have to be understood (click here) .

Next post on the Big O notation for representing remainder of a particular Taylor Series


Saturday, April 18, 2015

Agent-Based Simulation

ABS , a relatively new topic of research , is an interesting approach forward to learn how organisations of independent entities behave and respond to changes in the society. Recently , I had to present on the same for a class presentation , and on brushing up what i knew previously , i notice that this approach has finally encroached into business , which are using this to provide service oriented products ; behaviour of customers in supermarkets , behavior of an organisation of people in companies.A huge unheralded aspect of this is utilization in policy analysis. Once , efficient and sufficient frameworks for developing an Agent-Based Modelling arise , very well we can witness it being used by governments to decide on the policies they take.

The prospects of ABS are very enticing , however the computational complexity involved in creating entities with the characteristic behavior of real-life agents in quite challenging , in the least.

NetLogo is an open source software to program simple and relatively complicated agent dynamics.The key issue facing development of such simulations is the lack of a definite framework. That said , lots of interesting research applications already exist using ABS.

Sunday, March 16, 2014

Decision Making : a benchmark of AI capabilities

Decision Making is what classifies levels of intelligence in sentient beings.The ability to set upon a course of action when faced with a situation .In primitive intelligence like those of most animals,the course of actions under any situation are only achieving a source of food or obtaining a reproductive mate.The course of action predominantly seeks to attain any of these .In humans we have a much more complex (if not wide) decision making platform.Any event or situation we face seeks us to produce an action which is unique to our thinking , aspirations .So something like this which is so fundamental to our progress is undoubtedly an indication of our intelligence.
                                                        In AI, there is an amount of intelligence that the beings obtain from 'learning' through information that is passed to them externally not as what they experience/witness but rather from what is pre-programmed into them.This works well if we can ensure they are to work only in environments that are already fed/mapped into the AI systems.One might ask at this point as to why can't we program or map the entire world into them.Not bad an idea that ,but the time and effort required are way too costly to be put into effect.The real test for AI as a 'being' arises when we evaluate its performance in a new environment;what decision it takes to interact,communicate,perform activities and other features characteristic of a sentient being.....Next few posts on the levels of decision making we have achieved so far and its implications in the society
 

Monday, February 10, 2014

Genetic Algorithm

So an interesting phenomenon in nature is the process of evolution how we have come to adopt suitable characteristics over generations to adapt better to our environment and thus develop traits unique to families,societies,countries,continents...
And all that we have figured out about Genetics and Evolution has been successfully mimicked through the Genetic Algorithm...