Algorithm Analysis Term Project Topic: Social Network Structures (Graph Algorithms)
Budget: $10 – $30 USD
NOT : The code must be written in C programming, and the deadline is tomorrow at 3:00 PM.
Problem: Social networks are represented as graphs connecting individuals (nodes) with their friendships (edges). Community detection aims to identify groups of individuals in a social network graph that have stronger connections or interactions compared to the rest of the network.
For this project, you are expected to design an algorithm to detect communities in a given social network graph. The primary objective is to identify each group (community) within the network and its constituent nodes. The communities should be partitioned in a way that the nodes within them have stronger connections to each other than to nodes in other communities.
Operations: When designing your algorithm, perform the following steps.
1- Edge Betweenness: Edge betweenness measures how often the shortest path between two nodes passes through a particular edge. Calculate the edge betweenness values for the edges in the graph.
2- Remove the edge with the highest betweenness value to weaken the connections in the graph. This modification changes the structure of the graph, potentially separating communities.
3-Repeat the above steps until a certain criterion is met. Your program should be able to work with different criteria, as described below.
a. If, for k consecutive iterations, the number of communities remains the same, terminate the algorithm and print the number of communities along with their member information.
b. When the number of members in a community falls below a minimum threshold, t, terminate the algorithm and print the number of communities along with their member information.
Calculation of Edge Betweenness:
1-Choose node X and perform a BFS (Breadth-First Search) to find the number of shortest paths from X to every other node. Assign these numbers as scores to each node.
2-Calculate the edge scores for all edges in graph G, and repeat the process starting from step 1 for all nodes.
3-Sum up all the edge credits calculated in step 2 and divide by 2.
Problem: Social networks are represented as graphs connecting individuals (nodes) with their friendships (edges). Community detection aims to identify groups of individuals in a social network graph that have stronger connections or interactions compared to the rest of the network.
For this project, you are expected to design an algorithm to detect communities in a given social network graph. The primary objective is to identify each group (community) within the network and its constituent nodes. The communities should be partitioned in a way that the nodes within them have stronger connections to each other than to nodes in other communities.
Operations: When designing your algorithm, perform the following steps.
1- Edge Betweenness: Edge betweenness measures how often the shortest path between two nodes passes through a particular edge. Calculate the edge betweenness values for the edges in the graph.
2- Remove the edge with the highest betweenness value to weaken the connections in the graph. This modification changes the structure of the graph, potentially separating communities.
3-Repeat the above steps until a certain criterion is met. Your program should be able to work with different criteria, as described below.
a. If, for k consecutive iterations, the number of communities remains the same, terminate the algorithm and print the number of communities along with their member information.
b. When the number of members in a community falls below a minimum threshold, t, terminate the algorithm and print the number of communities along with their member information.
Calculation of Edge Betweenness:
1-Choose node X and perform a BFS (Breadth-First Search) to find the number of shortest paths from X to every other node. Assign these numbers as scores to each node.
2-Calculate the edge scores for all edges in graph G, and repeat the process starting from step 1 for all nodes.
3-Sum up all the edge credits calculated in step 2 and divide by 2.