$(20$ points$)$ Consider the following procedure for drawing a signed, complete graph from a

given social$-$affiliation network:

$($i$)$ Start with a social$-$affiliation network $S$ that has $n_p>1$ people and $n_f>0$ foci; note that

this network does not have to be connected, but each focus has to be connected to at least one

person node by an edge.

$($ii$)$ Make all person$-$person edges in this starting network positive.

$($iii$)$ For every pair of person nodes in the network that aren't connected by an edge, draw a

positive edge between them if that edge is an example of triadic or focal closure.

$($iv$)$ Keep repeating step $($iii$)$ on the modified graph until there are no more edges to draw that

are examples of triadic or focal closure.

$($v$)$ Finally, draw a negative edge between every pair of person nodes that isn't connected by

an edge after step $($iv$).$

The graph among the $n_p$ person nodes is now a complete signed graph G $.$

a$.$ Prove that G must be weakly balanced without using your answers to parts $b-c.$

b$.$ Let C be a connected component of S where there is at least one pair of person nodes

not connected by an edge. Prove that there is at least one pair of person nodes that is

not connected by an edge, where adding such an edge would be an instance of triadic

or group closure.

Hint: One way to approach the proof is as follows: Consider a pair of person nodes, $x$

and $y,$ that are not connected by an edge. Since $C$ is connected, there are two cases.

Case $1$: $x$ and $y$ have a common neighbor $n($where $n$ may be a person or focus$).$ Case

$2$: $x$ and $y$ do not have a common neighbor, and the shortest path between them has at

least two other nodes on it $x-n1-n2-$dots$-y($where each $n_i$ may be a person or

focus$).$ Then for each case, you can write a proof that there is at least one pair of

person nodes that is not connected by an edge, where adding such an edge would be

an instance of triadic or group closure.

c$.$ Let $k$ be the number of connected components in S$.$ Prove that G will have $k$ groups

of nodes such that each node has positive edges to nodes in its group and negative

edges to nodes in all other groups.

Hint: it may help to use the result you proved in part $($b$).$

d$.$ Draw an example of a social$-$affiliation network that has $($i$)$ at least two people, $($ii$)$ at

least one focus, $($iii$)$ each focus is connected to at least one person by an edge, and

$($iv$)$ where the signed complete graph formed after running the procedure above is not

balanced. Draw the starting social$-$affiliation network, explain what positive and

negative edges are drawn in by the procedure to form the signed complete graph, and

explain why the final signed complete graph is not balanced.

Hint: think about what part $($c$)$ suggests about the initial network's structure.