## 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.