pythonadvanced60 minutes

Advanced Social Network Graph Analyzer in Python

Build a Python mini-project that processes and analyzes a social network graph to extract insights such as influential users, community detection, and shortest connection paths.

Challenge prompt

You are tasked to create a Python program that models a social network graph where users are nodes and friendships are edges. Your program should support the following functionalities: 1) Add users and friendships, 2) Detect communities using a clustering algorithm, 3) Identify the top 3 most influential users based on the number of connections and centrality, and 4) Find the shortest connection path between two given users. Implement efficient data structures and graph algorithms to handle these operations on potentially large datasets.

Guidance

• Use adjacency lists or dictionaries to represent the graph for efficient relationship lookups.
• Consider algorithms like BFS or Dijkstra for shortest path calculations.
• Explore community detection algorithms such as Girvan-Newman or Louvain method for clustering.
• Develop a centrality metric (degree centrality or betweenness centrality) to rank user influence.

Hints

• Leverage collections like defaultdict for graph construction to simplify edge insertions.
• Caching intermediate results like shortest paths or clustering outputs can improve performance.
• Use Python libraries like networkx if allowed for prototyping; otherwise, implement core graph algorithms yourself.

Starter code

class SocialNetworkGraph:
    def __init__(self):
        self.graph = {}

    def add_user(self, user_id):
        if user_id not in self.graph:
            self.graph[user_id] = set()

    def add_friendship(self, user1, user2):
        self.add_user(user1)
        self.add_user(user2)
        self.graph[user1].add(user2)
        self.graph[user2].add(user1)

    def find_shortest_path(self, start_user, end_user):
        # Implement BFS or other algorithm
        pass

    def detect_communities(self):
        # Implement community detection algorithm
        pass

    def get_top_influential_users(self, top_n=3):
        # Implement centrality measure and ranking
        pass

# Example usage:
# sn = SocialNetworkGraph()
# sn.add_friendship('Alice', 'Bob')
# sn.add_friendship('Bob', 'Charlie')
# print(sn.find_shortest_path('Alice', 'Charlie'))

Expected output

For the sample graph where Alice is connected to Bob and Bob to Charlie, the shortest path from Alice to Charlie should output ['Alice', 'Bob', 'Charlie']. Community detection may yield one community containing all three users. The top influential user would be Bob with 2 connections.

Core concepts

Graph Data StructuresGraph AlgorithmsCommunity DetectionCentrality Measures

Challenge a Friend

Send this duel to someone else and see if they can solve it.