<jupyter_start><jupyter_text>Week 3<jupyter_code>import networkx as nx
import matplotlib.pyplot as plt

%matplotlib inline<jupyter_output><empty_output><jupyter_text>Degree Centrality Identifies the most importante nodes in a network- Directed network: degree- Undirected network: in-degree and/or out-degree Directed Network: ```Centrailty(node) = degree(v) / (|all nodes| - 1)``````0 <= Centrality <= 1```   Example 1<jupyter_code>g = nx.karate_club_graph()
g = nx.convert_node_labels_to_integers(g, first_label=1)
pos = nx.kamada_kawai_layout(g)
nx.draw_networkx(g, pos)
nx.center(g)
nx.degree_centrality(g)[34] # 13/33
nx.degree_centrality(g)[33] # 12/33<jupyter_output><empty_output><jupyter_text>Example 2<jupyter_code>gd = nx.MultiDiGraph()
e = [
        ('A', 'B'), ('A', 'E'), ('A', 'N'),
        ('B', 'C'), ('B', 'E'),
        ('C', 'A'), ('C', 'D'),
        ('D', 'B'), ('D', 'E'),
        ('E', 'D'), ('E', 'C'),
        ('F', 'G'),
        ('G', 'A'), ('G', 'J'),
        ('H', 'G'), ('H', 'I'),
        ('I', 'G'), ('I', 'F'), ('I', 'J'),
        ('J', 'F'), ('J', 'O'),
        ('K', 'L'), ('K', 'M'),
        ('L', 'M'),
        ('N', 'L'), ('N', 'O'),
        ('O', 'K'), ('O', 'L'),('O','J')
    ]
gd.add_edges_from(e)
gd
pos = nx.kamada_kawai_layout(gd)
nx.draw_networkx(gd, pos)
# IN-degree
i = nx.in_degree_centrality(gd)
# OUT-degree
o = nx.out_degree_centrality(gd)
i['A'], o['A']<jupyter_output><empty_output><jupyter_text>Closenesse Centrality Nodes that are important, will be close to other nodes ![closeness centrality](./media/ccentrality.png)   Example 3<jupyter_code>pos = nx.kamada_kawai_layout(g)
nx.draw_networkx(g, pos)
cc = nx.closeness_centrality(g)
cc[32]
sum(nx.shortest_path_length(g, 32).values())<jupyter_output><empty_output><jupyter_text>Example 4 ![disconnected](./media/disconnected.png)<jupyter_code>nx.closeness_centrality(gd)<jupyter_output><empty_output><jupyter_text>![disconnected2](./media/disconnected2.png) The nx.closeness_centrality() method is already normalized by```( (n-1) / (|G|-1) )```*There's **no** need to do it manually, like in the lecture!*<jupyter_code>nx.closeness_centrality(gd)['L']<jupyter_output><empty_output><jupyter_text>Betweenness Centrality A node 'n' has high Betweenness Centrality if it appears a great number of times in the shortest paths between nodes 'u' and 'v' ![betweennes centrality](./media/beecentrality.png) Note that we can either **include** or **exclude** the node 'v' as an **endpoint** ![betweennes centrality 2](./media/beecentrality02.png) We consider Betweenness Centrality only for nodes who can be reached   Example 5<jupyter_code>g_noD = nx.DiGraph()
g_noD.add_edges_from([
    
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'A'),
    ('D', 'B'),
    ('D', 'C')
    
])
pos = nx.kamada_kawai_layout(g_noD)
nx.draw_networkx(g_noD, pos)<jupyter_output><empty_output><jupyter_text>If we calculate the BetCentrality for node 'D', it would have us dividing by zero. Hence, we assume it as undefined.   Example 6<jupyter_code>g = nx.Graph()
g.add_edges_from(
    [
        ('A', 'B'), ('A', 'C'),
        ('B', 'C'),
        ('C', 'D'),
        ('D', 'E'),
        ('E', 'F'), ('E', 'G'),
        ('F', 'G')
    ]
)
pos = nx.kamada_kawai_layout(g)
nx.draw_networkx(g, pos)
bcc = nx.betweenness_centrality(G=g, endpoints=False)
bcc
def maxKeyVal(x: dict):
    keys = list(x.keys())
    values = list(x.values())
    return keys[values.index(max(values))], max(list(x.values()))

def minKeyVal(x: dict):
    keys = list(x.keys())
    values = list(x.values())
    return keys[values.index(min(values))], min(list(x.values()))
maxKeyVal(bcc), minKeyVal(bcc)<jupyter_output><empty_output><jupyter_text>Normalization: BetCentrality values will be larger in graphs with many nodes.- Undirected Graphs:        ```1/2 * ((|N| - 1) * (|N| - 2))```- Directed Graphs        ```(|N| - 1) * (|N| - 2)```    nx.betweenness_centrality() method already has a 'normalized' parameter, True as default   Example 7 Betweeness Centrality can be cost intensive```O(|N|³)```which leads us to calculate it using samples from the graph<jupyter_code>g = nx.karate_club_graph()
g = nx.convert_node_labels_to_integers(g, first_label=1)
betCentrality = nx.betweenness_centrality(G=g, normalized=True, endpoints=False)
# Using (k = 10) samples
betCentrality_approx = nx.betweenness_centrality(G=g, normalized=True, endpoints=False, k=10)
from operator import itemgetter
# top 5 from bet
sorted(betCentrality.items(), key=itemgetter(1), reverse=True)[:6]
# top 5 from betCentrality_approx
sorted(betCentrality_approx.items(), key=itemgetter(1), reverse=True)[:6]<jupyter_output><empty_output><jupyter_text>Example 8 Compute the BetCentrality between two groups, source and target groups<jupyter_code>s_nodes = [34, 33, 21, 30, 16, 27, 15, 23, 10]
t_nodes = [1, 4, 13, 11, 6, 12, 17, 7]
betCen_subset = nx.betweenness_centrality_subset(G=g,
                                                sources=s_nodes,
                                                targets=t_nodes,
                                                normalized=True)
# top 5 from betCen_subset
sorted(betCen_subset.items(), key=itemgetter(1), reverse=True)[:6]<jupyter_output><empty_output><jupyter_text>Example 9 Use BetCentrality to find imoprtant edges<jupyter_code>betCen_edges = nx.edge_betweenness_centrality(G=g, normalized=True)
# top 5 from betCen_edges
sorted(betCen_edges.items(), key=itemgetter(1), reverse=True)[:6]<jupyter_output><empty_output><jupyter_text>Compute the BetCentrality between two edges groups, source and target groups<jupyter_code>betCen_edges_subset = nx.edge_betweenness_centrality_subset(G=g,
                                                            sources=s_nodes,
                                                            targets=t_nodes,
                                                            normalized=True)
# top 5 from betCen_edges_subset
sorted(betCen_edges_subset.items(), key=itemgetter(1), reverse=True)[:6]<jupyter_output><empty_output><jupyter_text><jupyter_code># shoud have done it before...

from operator import itemgetter

def orderDict(x: dict, desc=True):
    return sorted(x.items(), key=itemgetter(1), reverse=desc)<jupyter_output><empty_output><jupyter_text>Page Rank  *(Best applied for Directed Networks)* Suppose we have a network with n nodesEach node will have a rank of ```1/n```. That implies that the ```sum()``` of all ranks is always equal to ```1```Then, perform the ```PageRank Update Rule``` k times PageRank Update Rule:    Each node gives an equal share of its current PageRank to all the nodes to    whom it is linked   Example 10 Performing PageRake Update Rule for k = 2 ![pageRank for k = 2](./media/pageRankUpdateKIs2_01.png) ![pageRank for k = 2](./media/pageRankUpdateKIs2_02.png) ![pageRank for k = 2](./media/pageRankUpdateKIs2_03.png) If we continue increasing value of ```k```, usually, values start to converge and stabilize ![pageRank for k = 2](./media/pageRankUpdateKIs2_04.png)  Scaled Page Rank Random Walk of k steps:```Start on a random node, then choose an outgoing edge at random an follow it to the next node; repeat k times.```<jupyter_code># The graph from the picture above
g = nx.DiGraph()
g.add_edges_from([
    ('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'B'), 
    ('D', 'A'), ('D', 'C'), ('D', 'E'), ('E', 'A'), 
])
pos = nx.spring_layout(g)
nx.draw_networkx(g, pos)<jupyter_output><empty_output><jupyter_text>We can interpreter a PageRank value as the probability of landing on a node (*page*) after ```k``` steps. Hence, the probability of landing on node 'B' at the end of a random walk is higher   Example 11<jupyter_code>g_new = g.copy()
# g with new nodes 'F', 'G', and new edges
g_new.add_edges_from([('B', 'F'), ('B', 'G'), ('F', 'G'), ('G', 'F')])
pos = nx.spring_layout(g_new)
nx.draw_networkx(g_new, pos)<jupyter_output><empty_output><jupyter_text>Random walks will probably land on nodes 'F' or 'G', since either of them is only connected to each otherWe add a damping parameter ```alfa```. Changing the behaviour of our Random Walk:- Start a node 'v', then:    - With probabilty ```alfa```: choose an outgoing edge and follow it to the next node;    - With probabilty ```1 - alfa```: choose a random node and jump directly to it;    - Repeat ```k```timesNow we have a way out to not be locked on nodes 'F' or 'G'<jupyter_code># Simple PageRank
pr_g = nx.pagerank(g)
# PageRank for g_new
# nx.pagerank() already has a standard alpha parameter of 0.85
pr_gnew = nx.pagerank(g_new)
# but we can change it
pr_gnew_a = nx.pagerank(G=g_new, alpha=0.9)
orderDict(pr_g)
orderDict(pr_gnew)
orderDict(pr_gnew_a)<jupyter_output><empty_output><jupyter_text>Hubs and Authorities - Root: Set of highly relevant web pages. Potential authorities;- Base: Root nodes and any node that links to a node in root;- Hubs: Nodes that are not our target, but link to those who are;- Authorities: Interest node(s) "Hubs estimates the node value based on *outgoing links*Authorities estimates the node value based on the *incoming links*" Consider all the edges connecting nodes in the base set ![base](./media/base.png) Instead of calculating the PageRank for all nodes in the network, we begin with a subset of the network, trying to work with possible strong candidates   Example 12 HITS Algorithm:- Assign each node an ```Authtority & Hub Score``` of ```1```;- Apply the Authority Update Rule:    - Each node's authority score is the sum of ```hub scores```of each node that **points to it**    - Apply the Hub Update Rule:    - Each node's hub score is the sum of ```authority scores``` of each node that **it points to**    - Normalize Authority and Hub scores:    - ```auth(j) = auth(j) / sum(auth(i))```    - ```hub(j) = hub(j) / sum(hub(i))```- Repeat ```k``` times<jupyter_code>g = nx.DiGraph()
g.add_edges_from(
    [
        ('A', 'D'),
        ('B', 'C'), ('B', 'E'),
        ('C', 'A'),
        ('D', 'B'), ('D', 'C'),
        ('E', 'B'), ('E', 'C'), ('E', 'D'), ('E', 'F'),
        ('F', 'C'), ('F', 'H'),
        ('G', 'C'), ('G', 'A'),
        ('H', 'A')
    ]
)
pos = nx.kamada_kawai_layout(g)
nx.draw_networkx(g, pos)<jupyter_output><empty_output><jupyter_text>![hits_01](./media/hits01.png) ![hits_02](./media/hits02.png) ![hits_03](./media/hits03.png) ![hits_04](./media/hits04.png) For most networks, as ```k``` grows, the authority and hub scores do converge to a unique value  ![hits_05](./media/hits05.png)<jupyter_code>hub, autr = nx.hits(g)
orderDict(autr)[:3]
orderDict(hub)[:3]<jupyter_output><empty_output><jupyter_text>Nodes that have:- **incoming** edges from ```good hubs``` are ```good authorities```- **outgoing** edges to ```good authorities``` are ```good hubs```  Comparing Centrality Measures   Example 13<jupyter_code>g = nx.MultiDiGraph()
g.add_edges_from([
        ('1', '2'), ('1', '5'),
        ('2', '1'), ('2', '3'), ('2', '4'), 
        ('3', '1'), ('3', '2'), ('3', '4'), 
        ('4', '1'), ('4', '3'), 
        ('5', '1'), ('5', '6'), 
        ('6', '7'), ('6', '5'), 
        ('7', '6'), ('7', '8'), ('7', '9'), 
        ('8', '6'), ('8', '7'), ('8', '9'), 
        ('9', '6'), ('9', '8'), 
    ])

g
indg = orderDict(nx.in_degree_centrality(g))
ccen = orderDict(nx.closeness_centrality(g))
betcen = orderDict(nx.betweenness_centrality(g))
g_single = nx.Graph(g.to_undirected())
pgrk = orderDict(nx.pagerank(g_single))
hubs, autr = nx.hits(g_single)

hubs = orderDict(hubs)
autr = orderDict(autr)
import pandas as pd
col_names = ['in-degree', 'closeness', 'betweness', 'page rank', 'autr', 'hubs']
df = pd.DataFrame(columns=col_names)
df['in-degree'] = [n for n, v in indg]
df['closeness'] = [n for n, v in ccen]
df['betweness'] = [n for n, v in betcen]
df['page rank'] = [n for n, v in pgrk]
df['autr'] = [n for n, v in autr]
df['hubs'] = [n for n, v in hubs]
df<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17371168743684742, 'fraction_numerical': 0.01633546648703267, 'mean_word_length': 4.157186278766826, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 77, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '290645', 'license': 'MIT', 'n_tokens_mistral': 4414, 'n_tokens_neox': 4257, 'n_words': 1191, 'path': 'socialNetAnalysis/w3/notes.ipynb', 'repo_name': 'htbrandao/applied-social-network-analysis-in-python', 'size': '11876'}