際際滷

際際滷Share a Scribd company logo

Social Network Analysis (Part 2)

Download as PPTX, PDF
Vala Ali Rohani
Vala Ali Rohani

Everything is connected: people, information, events and places. A practical way of making sense of the tangle of connections is to analyze them as networks. The objective of this workshop is to introduce the essential concepts of Social Network Analysis (SNA). It also seeks to show how SNA may help organizations unlock and mobilize these informal networks in order to achieve sustainable strategic goals. After discussing the essential concepts in theory of SNA, the computational tools for modeling and analysis of social networks will also be introduced in this presentation.

1 of 32
Downloaded 42 times
Social Network Analysis Dr. Vala Ali Rohani Vala@um.edu.my VRohani@gmail.com Part 2: Centrality
different notions of centrality In each of the following networks, X has higher centrality than Y according to a particular measure Y X Y X X Y Y X indegree outdegree betweenness closeness
review: indegree Y X
trade in petroleum and petroleum products, 1998, source: NBER-United Nations Trade Data
Which countries have high indegree (import petroleum and petroleum products from many others) Saudi Arabia Japan Iraq USA Venezuela Quiz Q:
review: outdegree Y X
Social Network Analysis (Part 2)
Which country has low outdegree but exports a significant quantity (thickness of the edges represents $$ value of export) of petroleum products Saudi Arabia Japan Iraq USA Venezuela Quiz Q:
putting numbers to it Undirected degree, e.g. nodes with more friends are more central.
normalization divide degree by the max. possible, i.e. (N-1)
real-world examples example financial trading networks high in-centralization: one node buying from many others low in-centralization: buying is more evenly distributed
In what ways does degree fail to capture centrality in the following graphs? what does degree not capture?
Brokerage not captured by degree Y X
betweenness: capturing brokerage intuition: how many pairs of individuals would have to go through you in order to reach one another in the minimum number of hops? X Y
betweenness: definition 奪 CB (i) = gjk (i) /gjk j<k Where gjk = the number of shortest paths connecting jk gjk(i) = the number that actor i is on. Usually normalized by: CB ' (i) = CB (i ) /[(n -1)(n -2) /2] number of pairs of vertices excluding the vertex itself
betweenness on toy networks non-normalized version:
betweenness on toy networks non-normalized version: A B C D E A lies between no two other vertices B lies between A and 3 other vertices: C, D, and E C lies between 4 pairs of vertices (A,D),(A,E),(B,D),(B,E) note that there are no alternate paths for these pairs to take, so C gets full credit
betweenness on toy networks non-normalized version:
betweenness on networks non-normalized version: A B C E D why do C and D each have betweenness 1? They are both on shortest paths for pairs (A,E), and (B,E), and so must share credit: 遜+遜 = 1
Quiz Question What is the betweenness of node E? E
betweenness: example Ladas old Facebook network: nodes are sized by degree, and colored by betweenness.
Quiz Q: Find a node that has high betweenness but low degree
Quiz Q: Find a node that has low betweenness but high degree
closeness What if its not so important to have many direct friends? Or be between others But one still wants to be in the middle of things, not too far from the center
need not be in a brokerage position Y X Y X X X Y Y
closeness: definition Closeness is based on the length of the average shortest path between a node and all other nodes in the network Closeness Centrality: N 奪 棚 棚 -1 炭 炭 Cc (i) = d(i, j) j=1 辿 谷 湛 短 Normalized Closeness Centrality ' (i) = (CC (i)) /(N -1) CC
closeness: toy example A B C D E ' (A) = Cc d(A, j) N 奪 j=1 N -1 辿 棚 棚 棚 棚 谷 -1 湛 炭 炭 炭 炭 短 = 1+ 2 +3+ 4 4 辿 谷 棚 -1 = 湛 短 炭 辿 10 4 谷 棚 -1 = 0.4 湛 短 炭
closeness: more examples
Quiz Q: Which node has relatively high degree but low closeness?
Is everything connected?
Connected Components Strongly connected components Each node within the component can be reached from every other node in the component by following directed links Strongly connected components B C D E A G H F Weakly connected components: every node can be reached from every other node by following links in either direction A B C D E F G H A B C D E F G H Weakly connected components A B C D E G H F In undirected networks one talks simply about connected components
Giant component if the largest component encompasses a significant fraction of the graph, it is called the giant component http://ccl.northwestern.edu/netlogo/models/index.cgi

More Related Content

Social Network Analysis (Part 2)

  • 1. Social Network Analysis Dr. Vala Ali Rohani Vala@um.edu.my VRohani@gmail.com Part 2: Centrality
  • 2. different notions of centrality In each of the following networks, X has higher centrality than Y according to a particular measure Y X Y X X Y Y X indegree outdegree betweenness closeness
  • 4. trade in petroleum and petroleum products, 1998, source: NBER-United Nations Trade Data
  • 5. Which countries have high indegree (import petroleum and petroleum products from many others) Saudi Arabia Japan Iraq USA Venezuela Quiz Q:
  • 8. Which country has low outdegree but exports a significant quantity (thickness of the edges represents $$ value of export) of petroleum products Saudi Arabia Japan Iraq USA Venezuela Quiz Q:
  • 9. putting numbers to it Undirected degree, e.g. nodes with more friends are more central.
  • 10. normalization divide degree by the max. possible, i.e. (N-1)
  • 11. real-world examples example financial trading networks high in-centralization: one node buying from many others low in-centralization: buying is more evenly distributed
  • 12. In what ways does degree fail to capture centrality in the following graphs? what does degree not capture?
  • 13. Brokerage not captured by degree Y X
  • 14. betweenness: capturing brokerage intuition: how many pairs of individuals would have to go through you in order to reach one another in the minimum number of hops? X Y
  • 15. betweenness: definition 奪 CB (i) = gjk (i) /gjk j<k Where gjk = the number of shortest paths connecting jk gjk(i) = the number that actor i is on. Usually normalized by: CB ' (i) = CB (i ) /[(n -1)(n -2) /2] number of pairs of vertices excluding the vertex itself
  • 16. betweenness on toy networks non-normalized version:
  • 17. betweenness on toy networks non-normalized version: A B C D E A lies between no two other vertices B lies between A and 3 other vertices: C, D, and E C lies between 4 pairs of vertices (A,D),(A,E),(B,D),(B,E) note that there are no alternate paths for these pairs to take, so C gets full credit
  • 18. betweenness on toy networks non-normalized version:
  • 19. betweenness on networks non-normalized version: A B C E D why do C and D each have betweenness 1? They are both on shortest paths for pairs (A,E), and (B,E), and so must share credit: 遜+遜 = 1
  • 20. Quiz Question What is the betweenness of node E? E
  • 21. betweenness: example Ladas old Facebook network: nodes are sized by degree, and colored by betweenness.
  • 22. Quiz Q: Find a node that has high betweenness but low degree
  • 23. Quiz Q: Find a node that has low betweenness but high degree
  • 24. closeness What if its not so important to have many direct friends? Or be between others But one still wants to be in the middle of things, not too far from the center
  • 25. need not be in a brokerage position Y X Y X X X Y Y
  • 26. closeness: definition Closeness is based on the length of the average shortest path between a node and all other nodes in the network Closeness Centrality: N 奪 棚 棚 -1 炭 炭 Cc (i) = d(i, j) j=1 辿 谷 湛 短 Normalized Closeness Centrality ' (i) = (CC (i)) /(N -1) CC
  • 27. closeness: toy example A B C D E ' (A) = Cc d(A, j) N 奪 j=1 N -1 辿 棚 棚 棚 棚 谷 -1 湛 炭 炭 炭 炭 短 = 1+ 2 +3+ 4 4 辿 谷 棚 -1 = 湛 短 炭 辿 10 4 谷 棚 -1 = 0.4 湛 短 炭
  • 29. Quiz Q: Which node has relatively high degree but low closeness?
  • 31. Connected Components Strongly connected components Each node within the component can be reached from every other node in the component by following directed links Strongly connected components B C D E A G H F Weakly connected components: every node can be reached from every other node by following links in either direction A B C D E F G H A B C D E F G H Weakly connected components A B C D E G H F In undirected networks one talks simply about connected components
  • 32. Giant component if the largest component encompasses a significant fraction of the graph, it is called the giant component http://ccl.northwestern.edu/netlogo/models/index.cgi