Graph mining - To become a champion

Question	Answer
Degree of a vertex	Number of incident edges
P(k): probability that a randomly chosen vertex has degree k	P(k) = Nk/ N (Nk = #nodes with degree k)
The distance between two nodes	The number of edges along the shortest path connecting them
Betweenness centrality	How many times a node lies on shortest paths between other nodes. Rationale: "shortest paths = most efficient route to information"
Clustering coefficient (Triangle-based)	Network level: ratio triangles/ connected triples
Clustering coefficient (Ego-network-based)	Node level: percentage of edges among neighbors
Girwan-Newman algorithm	1.Calculate betweeness of all edges 2. Remove edge with highest betweeness 3. Recalculate betweeness of edges affected by removal 4. Repeat 2 and 3 until no edges remain
Modularity	Clustering quality function Image: Ss (binary/octet-stream)
Clique percolation method	An approach for analyzing the overlapping community structure of networks. (networks = clusters = modules)
Community (community structure)	A network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally. Image: Ss (binary/octet-stream)

Resource summary

	Created by Tyson Mcleod over 6 years ago