Social Network Analysis

In this lecture, we demonstrate the setting up of working environment using Miniconda on Windows. The installation of Miniconda is very straight forward asking for permissions and the installation directory. The website provide installation files and help for other OS as well. After installation check version of the conda to ensure successful installation. Create a working environment for running codes of the social network analysis course.

In this lecture, we extended the environment created for the project and have added Jupyter lab and NetworkX in it. Jupyter lab will help in writing Python code while NetworkX has many classes that will help us in Graph creation, manipulation and analysis.

In this lecture, we create an undirected graph and add nodes and edges to it. We have discussed that the nodes can be of any type. We also showed that nodes and edges can either be added one at a time or in bulk using lists. The built-in functions available, help in determining the number of nodes and edges in the graph.

This lecture discusses, the possibility of representing different real-world problems as a graph and then the need of applying the shortest path algorithms for optimization. Any problem where the objects or instances can be studied in relation to one another can be studied as a graph problem. Graphs allow having more resource rich analysis of the problem as compared to other types of analysis where the objects may be evaluated in isolation.

The lecture, explains the Dijkstra algorithm for finding the shortest path between nodes, starting from a single source. It also has a condition that the weights will always be positive. In any problem represented as a graph, the Dijkstra algorithm helps find how similar or dissimilar the two nodes based on the distance between them. It may be interpreted in many ways.

This lecture explains the working algorithm of the Dijkstra shortest path algorithm. It requires a single source node and can find the shortest path from the source to all the nodes in the graph. Generally, the target node is also known.

Explaining the working of Dijkstra algorithm with the help of an undirected graph example. Dijkstra algorithm can be used for both directed and undirected graphs. Undirected graphs can also be considered as bidirectional graphs, where an edge between two nodes mean that you can traverse that edge in either direction.

This video explains how the Dijkstra algorithm can be applied to directed graphs. The process is pretty much the same, however, this time we have to consider the directions of edges while considering paths from one node to another. Only the out-links can be used to reach from the source node to the target node. In case there is no such path, that would connect the source to the target, the path cost is infinity.

This video explains the computational cost of the Dijkstra algorithm. It uses two nested loops and has complexity of O(n2).

The Bellman-ford shortest path algorithm is an improvement on the Dijkstra shortest path algorithm, which allows the graph to have edges with negative nodes as well. Bellman-ford is more effective because it considers all nodes to re-calculate all the costs and make modification if the cost to reach a node is reducing after changes in the previous iteration.

The video explains the working of bellman-ford algorithm with the help of a sample graph. Negative weights are also used to see how it deals with negative weights, which was a limitation of the Dijkstra's algorithm.

Bellman-ford algorithm has an assumption that the graph must not have a negative cycle. A negative cycle is the one that has a net cost less than zero. So, the algorithm would stick in infinitely looping through a negative cycle and the costs will continue to drop.

Bellman-ford algorithm is computationally more expensive as compared to the Dijkstra's algorithm. However, it is capable of dealing with negative weights.

This video provides a comparative analysis of the two shortest path algorithms that we have covered. They are compared in terms of their computational cost, constraints, how frequently the costs are updated and their order of search.

This video explains how negative cycles can be identified in a sample graph. Different approaches can be used for this purpose, however, the bellman ford algorithm itself indicates if there is a negative cycle in a graph. To check it, just run bellman ford algorithm for an extra iteration.

Graph coloring is also an optimization technique that is used to assign resources to tasks under a constraint. The basic idea is to fill all the regions while using as fewer colors as possible. The colors are the resources and the regions are the tasks that need those resources. It also helps in parallelization as the constraint which is the regions sharing border a basically dependent tasks while others may be carried out in parallel.

Graph coloring applications are discussed in this video. Graph coloring can be used for a number of real world scenarios where there are limited resources that are to be shared across multiple tasks in such a way that the performance can be maximized (performing all the tasks) while consuming as fewer resources as possible.

This lecture explains the greedy graph coloring algorithm. It uses a sample example to elaborate on the working of assigning colors to regions or nodes in a graph, while making sure that no two adjacent nodes have the same color.

The video solves a sample graph coloring problem using greedy graph coloring. It doesn't require the nodes to be in any particular order. So, we have used a random order of nodes and have starting coloring the graph while observing the given constraint.

Greedy graph coloring does not require any particular ordering of nodes before assigning colors. A problem with this setup is that when the nodes are arranged in different orders, the minimum number of colors required to color that graph also varies. It means that there is one specific order of nodes for any kind of graph that will always ensure using the minimum number of colors or the global minima. It is explained with the help of an example, that how different number of minimum colors are used when the nodes are ordered differently.

In this lecture, the working algorithm of the Kempe graph coloring is explained. It puts specific importance on the ordering of the nodes in a graph for the graph coloring problem. It ensures global minima in terms of the resources or colors utilization for coloring a graph or performing certain activities. Once the idea ordering of nodes is identified, the coloring process is the same as in greedy graph coloring.

The video provides a working understanding of the Kempe algorithm with the help of an example.

This video explains how kempe graph coloring can be used for a rather difficult case. Its step-wise procedure is very simple and even a graph that may look very complex, it would still identify the ideal order and will determine if the graph can be colored with the given number of colors and then would assign colors to the nodes.

In this lecture we introduce link analysis as a collection of techniques that can be applied to data having relationships among its entities.

In this lecture, we discuss te degree centrality of a node considering the graph to be both as directional and undirectional.

In this lecture, we discuss closeness centrality for evaluating the importance of a node based on the network structure.

In this lecture, we discuss betweenness centrality and calculate it for few nodes in the given network.

In this lecture, we calculate the betweenness centrality for one more node, considering the graph to be directed one. With that, we conclude our discussion on centrality.

In this lecture, we discuss prestige for a node in a network. We also discussed its two types that are degree prestige and proxmity prestige. With the help of a sample network we calculated them for few nodes.

In this lecture, we discuss the page rank algorithm that has modified the proximity based prestige by associating weights to the votes it is either receiving directly from its neighbors or indirectly from the neighbors of its neighbors and so on. It penalizes the outlinks by dividing the page rank of a resource among the receivers of its in-links.

In this lecture, we make use of our sample network to evaluate the page rank algorithm and calculate the page ranks for all the nodes. We tried different initial page rank values for the nodes to start with and found the nodes to get arranged in the same order each time.

In this lecture, we evaluate the improved versions of page rank algorithms that are having changes proposed in the following research work. The formula gets slightly modified to refine the page rank scores of each page.