Graphs in social networks in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a graph in the context of social networks?

A graph is a way to represent social networks using nodes (people or entities) and edges (connections or relationships between them).

beginner

What do nodes and edges represent in social network graphs?

Nodes represent individuals or entities, while edges represent the relationships or interactions between them.

intermediate

What is the difference between directed and undirected edges in social network graphs?

Directed edges show one-way relationships (like following someone), while undirected edges show mutual relationships (like friendship).

intermediate

How can graphs help analyze social networks?

Graphs help find important people, detect communities, understand how information spreads, and identify patterns in social connections.

intermediate

What is a community in a social network graph?

A community is a group of nodes that are more connected to each other than to the rest of the network, showing close relationships or shared interests.

In a social network graph, what does an edge usually represent?

A A relationship or connection between two people

B A single person

C A group of people

D A message sent

Edges represent the connections or relationships between nodes (people) in the graph.

What type of edge would represent a 'following' relationship on social media?

A Undirected edge

B Weighted edge

C Directed edge

D No edge

A 'following' relationship is one-way, so it is represented by a directed edge.

What is a node in a social network graph?

A A connection between people

B A person or entity

C A message

D A group

Nodes represent individuals or entities in the network.

Why are communities important in social network graphs?

A They identify groups with strong connections

B They represent messages

C They remove connections

D They show isolated individuals

Communities reveal groups where members are closely connected, helping understand social structure.

Which of the following is NOT a use of graphs in social networks?

A Understanding information spread

B Detecting communities

C Finding important people

D Cooking recipes

Cooking recipes are unrelated to graph analysis in social networks.

Explain how a social network can be represented as a graph and what the nodes and edges mean.

Think about how friends or followers connect in a network.

Describe the difference between directed and undirected edges in social network graphs and give an example of each.

Consider how social media connections work.

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