Graphs in social networks in Data Structures Theory - Mini Project: Build & Apply

Graphs in Social Networks

📖 Scenario: Imagine you are analyzing a small social network where people are connected as friends. Each person is a node, and each friendship is an edge connecting two nodes.

🎯 Goal: You will build a simple representation of a social network using a graph structure. You will create the data, set a threshold for popular users, find users with many friends, and finally mark those popular users.

📋 What You'll Learn

Create a dictionary representing the social network graph with exact people and their friends

Add a variable for the minimum number of friends to be considered popular

Use a loop to find all popular users based on the threshold

Add a final dictionary marking popular users with a boolean value

💡 Why This Matters

🌍 Real World

Social networks use graphs to represent connections between people, helping to analyze relationships and suggest new friends.

💼 Career

Understanding graph structures is important for roles in data analysis, social media management, and software development involving network data.

1

Create the social network graph

Create a dictionary called social_graph with these exact entries: 'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice', 'David', 'Eve'], 'Charlie': ['Alice'], 'David': ['Bob'], 'Eve': ['Bob'].

Data Structures Theory

# Create the social_graph dictionary with the given people and their friends
# Your code here

Hint

Use a dictionary where keys are names and values are lists of friends.

2

Set the popularity threshold

Create a variable called popularity_threshold and set it to 2 to represent the minimum number of friends needed to be considered popular.

Data Structures Theory

social_graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice', 'David', 'Eve'],
    'Charlie': ['Alice'],
    'David': ['Bob'],
    'Eve': ['Bob']
}
# Create popularity_threshold variable and set it to 2
# Your code here

Hint

This variable helps decide who is popular based on friend count.

3

Find popular users

Create an empty list called popular_users. Use a for loop with variables user and friends to iterate over social_graph.items(). Inside the loop, if the length of friends is greater than or equal to popularity_threshold, append user to popular_users.

Data Structures Theory

social_graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice', 'David', 'Eve'],
    'Charlie': ['Alice'],
    'David': ['Bob'],
    'Eve': ['Bob']
}
popularity_threshold = 2
# Create popular_users list and find users with friends count >= popularity_threshold
# Your code here

Hint

Check each user's friend list length and add to popular_users if it meets the threshold.

4

Mark popular users in a dictionary

Create a dictionary called popularity_status using a dictionary comprehension. For each user in social_graph, set the value to true if user is in popular_users, otherwise false.

Data Structures Theory

social_graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice', 'David', 'Eve'],
    'Charlie': ['Alice'],
    'David': ['Bob'],
    'Eve': ['Bob']
}
popularity_threshold = 2
popular_users = []
for user, friends in social_graph.items():
    if len(friends) >= popularity_threshold:
        popular_users.append(user)
# Create popularity_status dictionary marking popular users as true, others as false
# Your code here

Hint

Use a dictionary comprehension to assign true or false for each user.

Practice

1. In a social network graph, what do the nodes usually represent?

easy

A. Posts or comments

B. Users or people

C. Groups or communities

D. Messages sent

Solution

1. Step 1: Understand graph components in social networks

   Graphs use nodes to represent entities. In social networks, these entities are usually users or people.

2. Step 2: Identify what edges represent

   Edges represent connections like friendships, not the nodes themselves.

3. Final Answer:

   Users or people -> Option B

4. Quick Check:

   Nodes = Users [OK]

Hint: Nodes = users, edges = friendships [OK]

Common Mistakes:

• Confusing nodes with edges
• Thinking nodes represent messages
• Mixing up groups with nodes

2. Which of the following correctly describes an undirected edge in a social network graph?

easy

A. It shows a mutual friendship between two users

B. It represents a user posting a message

C. It shows a one-way friendship from one user to another

D. It indicates a user joining a group

Solution

1. Step 1: Define undirected edge meaning

   An undirected edge means the connection goes both ways, showing mutual relationship.

2. Step 2: Apply to social network context

   In social networks, mutual friendship means both users are connected equally, matching undirected edges.

3. Final Answer:

   It shows a mutual friendship between two users -> Option A

4. Quick Check:

   Undirected edge = mutual friendship [OK]

Hint: Undirected edges mean two-way connections [OK]

Common Mistakes:

• Thinking undirected edges are one-way
• Confusing edges with user actions
• Mixing edges with posts or groups

3. Consider this simple social network graph represented as adjacency list:
{'Alice': ['Bob', 'Carol'], 'Bob': ['Alice'], 'Carol': ['Alice']}
How many direct friends does Alice have?

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Read Alice's adjacency list

   Alice's list shows ['Bob', 'Carol'], meaning Alice is directly connected to Bob and Carol.

2. Step 2: Count direct friends

   There are 2 names in the list, so Alice has 2 direct friends.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Length of Alice's list = 2 [OK]

Hint: Count names in adjacency list for direct friends [OK]

Common Mistakes:

• Counting indirect friends
• Confusing keys with values
• Ignoring list length

4. Given this adjacency list for a social network:
{'Dave': ['Eve'], 'Eve': ['Dave', 'Frank'], 'Frank': ['Eve']}
What is wrong if we add 'Frank' to Dave's list but forget to add 'Dave' to Frank's list?

medium

A. The graph will have a syntax error

B. The graph will show no connection between Dave and Frank

C. The graph becomes directed, showing one-way friendship

D. The graph will crash when accessed

Solution

1. Step 1: Understand undirected graph rules

   In undirected graphs, edges must be mutual. Adding Frank to Dave's list but not Dave to Frank's breaks this.

2. Step 2: Identify effect on graph type

   This creates a one-way connection, making the graph directed for that edge.

3. Final Answer:

   The graph becomes directed, showing one-way friendship -> Option C

4. Quick Check:

   Missing mutual edge = directed edge [OK]

Hint: Mutual edges needed for undirected graphs [OK]

Common Mistakes:

• Expecting syntax errors
• Assuming no connection exists
• Thinking graph will crash

5. A social network wants to suggest new friends by finding users who share at least two mutual friends but are not directly connected. Which graph concept helps solve this problem?

hard

A. Calculating node degrees

B. Finding shortest paths between nodes

C. Detecting cycles in the graph

D. Counting common neighbors between nodes

Solution

1. Step 1: Understand the friend suggestion criteria

   The network wants to find users not directly connected but sharing at least two mutual friends.

2. Step 2: Identify graph concept matching criteria

   Counting common neighbors (shared friends) between two nodes helps find such pairs.

3. Final Answer:

   Counting common neighbors between nodes -> Option D

4. Quick Check:

   Mutual friends = common neighbors [OK]

Hint: Mutual friends = common neighbors count [OK]

Common Mistakes:

• Using shortest paths incorrectly
• Confusing cycles with mutual friends
• Only checking node degrees