04 SNA Dense Subnetworks

Question 1

In how far can Emergence as a point of view mediate between individualistic and collectivistic points of view when investigating groups? (2 -3 sentences)

Answer 1

• Individualist school of thought: all phenomena and structures in a SN can be derived from analyzing dyadic individual relations vs. Collectivistic school of thought: assign reality and parameters to groups independent of its members.

Question 2

Nominate two characteristics of small groups!

Answer 2

• E.g. cliques: perfectly dense, perfectly compact

Question 3

What are quasi groups?

Answer 3

• People with no real social relation but put together in a group.

Question 4

Is a (Web-)community a group in the sociological sense? Give one supporting argument and one counterargument!

Answer 4

• Pro: Compactness: mean average path-length is small
• Con: Separation: group members don’t have more ties within the community than outside

Question 5

Can cliques overlap? Explain Your answer briefly!

Answer 5

• Yes, they can overlap without being identical
• Cliques are closed under exclusion: U \ {v € U} is still a clique
• Cliques are nested: Each clique U of size n contains n Cliques of size n-1

Question 6

Explain why N-cliques do not have to be connected!

Answer 6

• Since distance is evaluated with regards to G and not G([U]), N-cliques need not even be connected and can have a diameter diam(G([U])) > N

Question 7

Given the following definitions for alternative prototypes
‡ U is N-clique iff ׊u,v אV : distG(u,v) ൑ N
‡ U is N-club iff diam(G([U])) ൑ N
‡ U is N-clan iff U is maximal N-clique and diam(G([U])) ൑ N
Name all N-cliques, N-clubs, N-clans in the following graph!

Answer 7

• Maximal 2-cliques: {1, 2, 3, 4, 5}, {2, 3, 4, 5, 6} (+Power sets)
• 2-clubs: {1, 2, 3, 4}, {1, 2, 3, 5}, {2, 3, 4, 5, 6}
• 2-clan: {2, 3, 4, 5, 6}

Question 8

Are N-clubs closed under exclusion and are they nested? Explain briefly!

Answer 8

• No, they are neither closed under exclusion nor are they nested
• Example: A ring of 5 nodes (also a 2-club)
• Exclusion: diam(G[U]) <= 2, take one out and diam(G[U]) becomes <= 3
• Nested: Taking the same sub-graph as in Exclusion, diam(G[U]) <= 3

Question 9

What are considerations when choosing N if N-cliques are used as prototypes for social
groups in a social network?

Answer 9

• N should not be > 2, as that would defy the purpose of a clique/group/social
  network (N = 2 -> friend of a friend)
• Alternative explanation: Small distances are characteristic even for large social
  networks (comp. 6 degrees) => N-cliques may not be socially meaningful as
  groups (especially for larger N)

Question 10

Is the problem “Find the size k of a maximum clique of an undirected graph G“ efficiently
solvable?

Answer 10

• Naive algorithm: Compute all subsets of V and check for clique -> O (n² 2^n)
• (There are slightly optimized versions of said algorithm but nothing crazy)
• The decision problem CLIQUE (G, k): “Has G a clique of size at least k” is NP
  complete so it is not efficiently solvable unless P=NP (so not at the moment)