# CSE 6240 – Web Search & Text Mining Homework 7 solved

\$35.00

## Description

5/5 - (1 vote)

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’?
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
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:
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