2/22/2012...Introduction to graph Theory

In the lecture given by Dr. Sudha Ram on Graph theory, she started with Königsberg Graph's theory and the bridges that graph theory was all about edges, nodes and connecting them together. She discussed about Informational networks which help move information move from one place to another and how today they were looked in the context of social media. One major area of discussion was constructing a Collaboration Network where you try to find the shortest path between 2 nodes to build a transportation network with the help of hubs.

She told about degree which is number of links that are connected to a node. In-degree in which incoming edges are counted for a node and in out-degree outgoing edges are counted for a note.

Some questions which were answered were: what we are going to do to grow the nodes? How am I going to connect nodes in network using directed or undirected nodes?

We learned about the Giant graph component on web where significant portion or nodes o websites are connected to each other and there are very few nodes which are not connected to each other. Two huge graphs could be compared based on average degree, one with more average degree is well connected with another.

Another concept was Small World Phenomenon in which a study of WWW and social media shows that if we take any pair of nodes, there is a surprisingly less distance between two arbitrary nodes.

Below is a graph which I generated using Gephi from facebook data. In this case, the nodes are people and the edges show that one person is following another. Generated .gdf file using netvizz – facebook to gephi