SOCIAL NETWORKS ANALYSIS
ASSIGNMENT 2
SOCIAL NETWORK ANALYSIS. BASIC NETWORK MEASURES
| 1 THEORY |
| Social network analysis (SNA) measures are a vital tool for understanding the behavior of networks and graphs. These algorithms use graph theory to calculate the importance |
| of any given node in a network. Well implemented, SNA measures allow the analyst to cut through noisy data and hone into the parts of a network that require further attention. |
1.1 SNA MEASURE 1: DEGREE CENTRALITY
| Definition: Degree centrality assigns an importance score based purely on the number of links held by each node. What it tells us: How many direct, ‘one hop’ connections each node has to other nodes within the network. When to use it: For finding very connected individuals, popular individuals, individuals who are likely to hold most information or individuals who can quickly connect with the wider network. A bit more detail: Degree centrality is the simplest measure of node connectivity. Sometimes it’s useful to look at in-degree (number of inbound links) and out-degree (number of outbound links) as distinct measures, for example when looking at transactional data or account activity. For example, we have the undirected and unweighted Graph 1: |
| Degree centrality di for the node 6 is equal to d6=4 (four relationships – with nodes 8, 7, 5 and 4), but for Node 1 – is equal to d1=3 (three relationships – with nodes 2, 3 and 4). |
SOCIAL NETWORKS ANALYSIS
|
For example, we have the Undirected and Weighted graph 2:
2
12124
3
4
5
3
1 2 2 1 |
|
Weighted Degree centrality dWi for the node 6 is equal to dW6=11 (four relationships – with
nodes 8, 7, 5 and 4 with weights 2, 3, 5 and 1), but for Node 1 – is equal to dW1=7 (three
relationships – with nodes 2, 3 and 4 with weights 2, 4 and 1)
For example, we have the Directed and Weighted graph 3:
2
12124
3
5
3
1
2
Weighted OutDegree centrality dWOi for the node 6 is equal to dWO6=1 (one outcome relationship
with nodes 4 with weights 1), InDegree centrality dWIi for the node 6 is equal to dWI6=10 (three
Income relationships – with nodes 8, 7 and 5 with weights 2, 3 and 5).
4
1 2 |
1.2 SNA MEASURE 2: BETWEENNESS CENTRALITY
What it tells us:
1. How crucial is a person to the transmission of information through a network?
2. How many flows of information are disrupted or must make longer detours if a person
stops passing on information or disappears from the network?
Definition: Betweenness centrality measures the number of times a node lies on the shortest path between other nodes.
3. To what extent may a person control the flow of information due to his or her position in
the communication network?
When to use it: For finding the individuals who influence the flow around a system.
SOCIAL NETWORKS ANALYSIS
A bit more detail: Betweenness is useful for analyzing communication dynamics, but should be used with care. A high Betweenness count could indicate someone holds authority over, or controls collaboration between, disparate clusters in a network; or indicate they are on the periphery of both clusters.
Betweenness centrality could be calculated by the counting how many shortest paths between two actors nj and nk contain actor ni?
Bd (ni ) g jk (ni ) , jk gjk
gik – the number of shortest paths from nj to nk
gjk (ni) – the number of shortest paths that contain point ni as an intermediary in the shortest
paths from nj to nk.
For the node 4 the Betweenness centrality is equal to Bd (n4 ) 15 .
| For undirected and unweighted Graph 1 |
| g jk (ni ) gjk | k=1 | K=2 | K=3 |
| j=5 | 1/1 | 2/2 | 1/1 |
| j=6 | 1/1 | 2/2 | 1/1 |
| j=7 | 2/2 | 4/4 | 2/2 |
| j=8 | 2/2 | 4/4 | 2/2 |
| j=9 | 2/2 | 4/4 | 2/2 |
| Sum | 15 |
| 1.3 SNA MEASURE 3: CLOSENESS CENTRALITY |
| Definition: This measure scores each node based on their ‘closeness’ to all other nodes within |
|
the network. What it tells us: This measure calculates the shortest paths between all nodes, then assigns each node a score based on its sum of shortest paths. When to use it: For finding the individuals who are best placed to influence the entire network most quickly. A bit more detail: Closeness centrality can help find good ‘broadcasters’, but in a highly connected network you will often find all nodes have a similar score. What may be more useful is using Closeness to find influencers within a single cluster. |
L(ni ,nj ) – the shortest distance between ni to nj
SOCIAL NETWORKS ANALYSIS
The Closeness centrality of a node is based on the total distance between one node and all other
nodes, where larger distances yield lower closeness centrality scores.
The closer a node is to all other nodes, the easier information may reach it, the higher its
Closeness centrality.
Сd(ni) g
1 L(n,n )
ij i 1
| For undirected and unweighted Graph 1: | ||||||||||
| L(ni,nj) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ∑ |
| 1 | – | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 17 |
| 2 | 1 | – | 1 | 2 | 3 | 3 | 4 | 4 | 5 | 23 |
| 3 | 1 | 1 | – | 1 | 2 | 2 | 3 | 3 | 4 | 17 |
| 4 | 1 | 2 | 1 | – | 1 | 1 | 2 | 2 | 3 | 13 |
| 5 | 2 | 3 | 2 | 1 | – | 1 | 1 | 1 | 2 | 13 |
| 6 | 2 | 3 | 2 | 1 | 1 | – | 1 | 1 | 2 | 13 |
| 7 | 3 | 4 | 3 | 2 | 1 | 1 | – | 1 | 1 | 16 |
| 8 | 3 | 4 | 3 | 2 | 1 | 1 | 1 | – | 2 | 17 |
| 9 | 4 | 5 | 4 | 3 | 2 | 2 | 1 | 2 | – | 17 |
| ∑ | 17 | 23 | 17 | 13 | 14 | 14 | 16 | 17 | 17 | – |
Forthenode4the Closenesscentralityisequalto Сd(n4)1/130,076923,forthenode 2 the Closeness centrality is equal to Сd (n2 ) 1 / 23 0,043478
What it tells us: By calculating the extended connections of a node, EigenCentrality can identify nodes with influence over the whole network, not just those directly connected to it.
| 1.4 SNA MEASURE 4: EIGENCENTRALITY |
| Definition: Like degree centrality, EigenCentrality measures a node’s influence based on the number of links it has to other nodes within the network. EigenCentrality then goes a step further by also taking into account how well connected a node is, and how many links their connections have, and so on through the network. |
SOCIAL NETWORKS ANALYSIS
Highly connected individuals within highly interconnected clusters, or ‘big fish in big ponds’, have high eigenvector centrality
When to use it: EigenCentrality is a good ‘all-round’ SNA score, handy for understanding human
social networks, but also for understanding networks like malware propagation.
A bit more detail: KeyLines calculates each node’s EigenCentrality by converging on an
eigenvector using the power iteration method
| 1.5 SNA MEASURE 5: PAGERANK |
| Definition: PageRank is a variant of EigenCentrality, also assigning nodes a score based on their connections, and their connections’ connections. The difference is that PageRank also takes link direction and weight into account – so links can only pass influence in one direction, and pass different amounts of influence. |
|
What it tells us: This measure uncovers nodes whose influence extends beyond their direct
connections into the wider network. When to use it: Because it factors in directionality and connection weight, PageRank can be helpful for understanding citations and authority. A bit more detail: PageRank is famously one of the ranking algorithms behind the original Google search engine (the ‘Page’ part of its name comes from creator and Google founder, Sergei Brin). |
| 2 TASKS |
| 1. Study the following training materials for basic skills of working with Gephi: https://gephi.org/tutorials/gephi-tutorial-quick_start.pdf |
2. Create your own Graph (Data Laboratory) which describes the one of the models of Social Networks: relationship between companies or company departments, your group members, your colleagues at work, in your family, at a sports club, a student organization, and so on.
3. As the Weight of described relationship can be used: number of messages sent to each other
- number of common projects
- degree of trust
- number of views for advice etc.
- Visualize your Network by using the most appropriate Layout.
- Calculate the Basic Indicators for this Graph:
- Number of Nodes,
- Number of Edges,
- Average Path Length,
- Graph Density.
SOCIAL NETWORKS ANALYSIS
What can you say about the general structure of network?
6. Calculate the basic Centrality measures for the Graph’s nodes (∑Statistics)
- Degree,
- Weighted Degree,
- Closeness,
- Betweenness,
- EigenVector.
| 7. Select and represent the nodes in the table with the highest values of each indicator. 8. Visualize the different Centrality measures of each node by the Size and Colors of the nodes (Partition, Ranking). |
| 9. Identify the Communities in your Network using Modularity algorithm. Explain the reasons of appearance of such communities. 10. Use the Filters (Partition, Range, Topology) for showing the different groups od nodes. 11. Analyze the Ego-networks for the most interesting (for your network) Nodes. 12. Fill the following table by Nodes from your Network and give the explanation (Labels) of each Node phenomena. |
3 REPORT STRUCTURE
- The Purpose of the study.
- The Object of study.
- The Tasks that need to be solve in the research process.
- Research Methods that have been used
- General Concepts of social networks analysis theory (introduction)
- Problem statement.
- Results of the study.
- The Conclusions of your research. What the consequences can be in accordance with the conclusions you have received (for company, for your relationships etc.)?
SOCIAL NETWORKS ANALYSIS