Graph Element Analysis图形元素的分析.pptVIP

Graph Element Analysis Woochang Hwang Department of Computer Science and Engineering State University of New York at Buffalo Introduction Real World Networks Centralities Motivation Bridging Centrality Bridge Cut Discussion Future Works Introduction Many real world systems can be described as networks. Social relationships: e.g. collaboration relationships in academic, entertainment, business area. Technological systems: e.g. internet topology, WWW, or mobile networks. Biological systems: e.g. regulatory, metabolic, or interaction relationships. Almost all of these real world networks are Scale-free. Real World Networks Yeast PPI network Real World Networks Proteom Size (PDB) Real World Networks Power law degree distribution: Rich get richer Small World: A small average path length Mean shortest node-to-node path Can reach any nodes in a small number of hops, 5~6 hops Robustness: Resilient and have strong resistance to failure on random attacks and vulnerable to targeted attacks Hierarchical Modularity: A large clustering coefficient How many of a node’s neighbors are connected to each other Disassortative or Assortative Biological networks: disassortative Social networks: assortative Real World Networks Real World Networks Real World Networks Real World Networks Robust. For ?3, removing nodes does not break network into islands. Very resistant to random attacks, but attacks targeting key nodes are more dangerous. Centralities Degree centrality: number of direct neighbors of node v where N(v) is the set of direct neighbors of node v. Stress centrality : the simple accumulation of a number of shortest paths between all node pairs where ρst(v) is the number of shortest paths passing through node v. Centralities Closeness centrality: reciprocal of the total distance from a node v to all the other nodes in a network δ(u,v) is the distance between node u and v. Eccentricity: the greatest distance between v and any other ver