Description
1. Strong and weak ties in the network (50%)
a) What is ‘Strong Triadic Closure Property’? Using a graph example, show in
detail how it is used to prove the theorem on local bridges and weak ties
mentioned on page 17 of slides ‘lecture 10.3’. (10%)
b) In the following 3 networks (figure 1, 2, 3) with each edge labeled as either a
strong or weak tie, which nodes violate the ‘Strong Triadic Closure Property’?
Explain your answer. (15%) (strength d-c in figure 1 is missing. Please work
on both cases)
Figure 1
Georgia Institute of Technology CSE6240 – Homework 7
Figure 2
Figure 3
c) Show the process of partition the following graph (figure 4) using GirvanNewman method. (Please refer to NCM chapter 3.6 for G-N method) (25%)
Georgia Institute of Technology CSE6240 – Homework 7
Figure 4
2. Structural Balance in Social Networks (50%)
a) Consider the 3-node social networks in Figure 5, 6, 7, in which all pairs of
nodes know each other, and each pair is either friendly or hostile as indicated
by the ‘+’ or ‘-‘ label on each edge. A fourth node D wants to join this
network, and establish either positive or negative relations with each existing
node A, B, and C. For each case, can node D do this in such a way that it
doesn’t become involved in any unbalanced triangles? If there is a way for D
to do this, say how many different such ways there are, and give an
explanation. Otherwise, give an explanation why not. (30%)
Figure 5
Georgia Institute of Technology CSE6240 – Homework 7
Figure 6
Figure 7
b) Using what you’ve worked out in Questions a, consider the following
question. Take any labeled complete graph on any number of nodes that is
not balanced; i.e. it contains at least one unbalanced triangle. (Recall that a
labeled complete graph is a graph in which there is an edge between each
pair of nodes, and each edge is labeled with either + or -.) A new node X
wants to join this network, by attaching to each node using a positive or
negative edge. When, if ever, is it possible for X to do this in such a way that
it does not become involved in any unbalanced triangles? Give an
explanation for your answer and prove it. (Hint: Think about any unbalanced
triangle in the network, and how X must attach to the nodes in it.) (20%)
3. (Bonus) Write a program checking if a graph is balanced or not. (50%)
Given an UNDIRECTED graph, your program should read a number of signed
edges and output ‘YES’ if it is balanced and ‘NO’ if not. Please refer to the slides
for the algorithm and follow the INSTRUCTIONS below.
Input format:
Your program should read from STANDARD INPUT stream.
The first line contains two integers, n and m, denoting number of nodes
and edges. Nodes range from 0 ~ n-1 and n will be maximally 1,000,000.
Georgia Institute of Technology CSE6240 – Homework 7
The following m lines describe m edges. Each line contains two integers x,
y, and a sign ‘+’ or ‘-‘, denoting a signed undirected edge between x and y. There
is NO self-loop and NO duplicate edges.
Output format:
Your program should write to STANDARD OUTPUT stream.
If the graph is balanced, output ‘YES’. Otherwise, output ‘NO’.
Sample Input:
5 4
1 2 +
3 4 +
4 5 –
5 3 +
Sample Output:
NO
Below are some instructions:
a. Your program should contain only ONE file, naming
checkBalance_LASTNAME_FIRSTNAME.xxx where xxx is the possible
extension (java, c, cpp, py). Please upload it along with your report
directly (don’t use zip and no need to write readme or report).
b. Your program should NOT assume any command line parameters like
input/output files. It should directly read from standard input and
write to standard output.
c. You may write in any language you like, but please be prepared to
demo in TA hour if it is none of C++, Java and Python or it uses any
third-party libraries.
