Key Node ldentification Graph Mining m即 Canada Hudson Bay Mentana Great Vermont Nebraska Illinois -Rhode Island Missouri West United States Delaware Kentucky入-virginia Maryland of America Washington,DC N店t丙 Oklahoma Atlantic Ocean Alabamd 用 worldatlas Gulf 350m Mexico 350am Mexlco Bahamas Cuba 45 23:15EST 14 A1g.2003 It powered cut on a large scale in America
It powered cut on a large scale in America. Key Node Identification Graph Mining
Key Node ldentification Graph Mining Which key electronic stations do we protect to avoid all electronic network shut down when some electronic stations damage
Which key electronic stations do we protect to avoid all electronic network shut down when some electronic stations damage ? Key Node Identification Graph Mining
Key Node ldentification Graph Mining Strategy ONE:Centrality >Degree Centrality: The size of connections is used to measure node importance(the node's direct influence). k DC(①)=N-1 Betweenness Centrality: The betweenness centrality for each vertex is the number of these shortest paths that pass through the BC(i) gst vertex. >Closeness Centrality: To calculate as the sum of the length of the shortest paths between the node and all other nodes in the d graph
¾ Degree Centrality: The size of connections is used to measure node importance(the node’s direct influence). ¾ Betweenness Centrality: The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex. ¾ Closeness Centrality: To calculate as the sum of the length of the shortest paths between the node and all other nodes in the graph. Strategy ONE: Centrality 1(݅) = ܥܥ ݀ ୀଵ ௦௧(݅) =݃ܥܤ ݃௦௧ ஷ௦ஷ௧ = (݅)ܥܦ ݇ ܰ − 1 Key Node Identification Graph Mining
Key Node ldentification Graph Mining Strategy TWO:K-shell Decomposition Layer or shell. More central,more influential k=1 >Advantage: Low computational complexity. (a) (b) Reveal the hierarchy structure clearly. Disadvantage: 00 Can't be used in quite a lot networks, ks=2 such as the star network,tree and so on. 。1 Too coarse,some times is inferior to degree measure. (d)
¾ Layer or shell. ¾ More central, more influential. ¾ Advantage: • Low computational complexity. • Reveal the hierarchy structure clearly. ¾ Disadvantage: • Can’t be used in quite a lot networks, such as the star network, tree and so on. • Too coarse, some times is inferior to degree measure. Strategy TWO: K-shell Decomposition Key Node Identification Algorithms Graph Mining