Wednesday, October 9, 2013

Introduction to Network Analysis terminology

Part of the Network

Node: Nodes are the entities in graph. Eg. If we consider Facebook friends as a graph then every friend is a node.

Edge: These are the relationships between between nodes. Eg. If we consider Facebook friends as a graph then every friendship is an edge.

Types of the Network

Undirected vs Directed

Undirected graph: When the relationship of edge is always valid in both directions then it is called undirected graph. If Dave is friend with Raj on Facebook then Raj is also friend with Dave.

Directed graph: When the relationship may not be valid in both direction (connecting nodes) then it is called directed graph. If Bill is following Steve on Twitter and Steve is not following Bill.

Single-mode vs Multi-mode

Single-mode graph: It is type of graph where all nodes from a graph belong to same category. A graph of Facebook friends where every node is a person.

Multimode graph: It is type of graph where all nodes are not of same type. A graph where we have buyers and sellers connected with relationship called deals is multi-mode graph.

Weighted vs Unweighted

Weighted network: A network where the edges between nodes have weights assigned to them.

Unweighted Network: A network where the edges between network do not have weights assigned or treated as units weight for all edges.

Centrality measure of network

Every single node in the network will have following centrality measures.

Degree Centrality: Number of edges connected with a particular node define the degree centrality of the node.

Betweenness centrality:  Number shortest paths between all nodes in a network which pass through a given node, defines the betweenness centrality of that node.

Closeness centrality: Length of average shortest path between a given node and all other nodes in a graph.

Eigenvector centrality: This is a measure of influence of a given node in the whole network. The notion is how well connected a given node is with other well connected nodes in the network.

The most important measure of centrality would be Eigenvector centrality. Google's page rank is variation of Eigenvector centrality measure. Even in genetic network analysis it is widely used.

Other important network terms
Fully-connected graph: When there is a relationship (edge) connecting every node with all other nodes. A fully connected graph with n nodes will have n(n-1)/2 edges.

Average Path Length: It is the average number of hops along the shortest path it takes to reach from one node to the other within a network. It also measure the degrees of separation between two nodes in the network.

Network Diameter: The longest of all shortest paths between two nodes in a network. It measures how far are the most distant nodes from each other.

Density: For a graph its density is the ratio of number of edges in the network to the total possible edges in a network. [ Density = no of edges/ (n (n-1) / 2) ]

Modularity: It represents the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules.

Average Degree: It is number of edges in comparison with number of nodes. For an undirected graph average degree is 2(E/N).

Average network coefficient: For a given node clustering coefficient represents density of network formed by other nodes who are directly connected with the given node. Similarly clustering coefficient for a given network is average of all coefficients for all nodes within a network.

[ Image source : wikipedia ]

No comments:

Post a Comment