Exercises

1. Suppose that a team of anthropologists is studying a set of three small villages that neighbor one another. Each village has 30 people, consisting of 2-3 extended families.

Everyone in each village knows all the people in their own village, as well as the people in the other villages.

When the anthropologists build the social network on the people in all three villages taken together, they find that each person is friends with all the other people in their own village, and enemies with everyone in the two other villages. This gives them a network on 90 people (i.e., 30 in each village), with positive and negative signs on its edges.

According to the definitions in this chapter, is this network on 90 people balanced? Give a brief explanation for your answer.

2. Consider the network shown in Figure 5.18: there is an edge between each pair of nodes, with five of the edges corresponding to positive relationships, and the other five of the edges corresponding to negative relationships.

Each edge in this network participates in three triangles: one formed by each of the additional nodes who is not already an endpoint of the edge. (For example, the A-B edge participates in a triangle on A, B, and C, a triangle on A, B, and D, and a triangle on A, B, and E. We can list triangles for the other edges in a similar way.)

For each edge, how many of the triangles it participates in are balanced, and how many are unbalanced. (Notice that because of the symmetry of the network, the answer will be the same for each positive edge, and also for each negative edge; so it is enough to consider this for one of the positive edges and one of the negative edges.)

3. When we think about structural balance, we can ask what happens when a new node tries to join a network in which there is existing friendship and hostility. In Fig-ures 5.19–5.22, each pair of nodes is either friendly or hostile, as indicated by the + or−label on each edge.

First, consider the 3-node social network in Figure 5.19, in which all pairs of nodes know each other, and all pairs of nodes are friendly toward each other. Now, a fourthnode D wants to join this network, and establish either positive or negative relations with each existing node A,B, and C. It wants to do this in such a way that it doesn’t become involved in any unbalanced triangles. (I.e. so that after adding D and the labeled edges from D, there are no unbalanced triangles that contain D.) Is this possible? In fact, in this example, there are two ways for Dt o accomplish this, as indicated in Figure 5.20. First, D can become friends with all existing nodes; in this way, all the triangles containing it have three positive edges, and so are balanced. Alternately, it can become enemies with all existing nodes; in this way, each triangle containing it has exactly one positive edge, and again these triangles would be balanced .So for this network, it was possible for D to join without becoming involved in aGraph Theory

Recap from the last week

Importance and definition of a network

Two levels of understanding:

(1) at the level of structure Graph theory

(2) at the level of behavior Game theory

The next three weeks’ topic

What is a social network? Relations among People

https://ocw.mit.edu/courses/sloan-school-of-management/15-599-workshop-in-it-collaborative-innovation-networks-fall-2011/lecture-notes/MIT15_599F11_lec04.pdf

What is a Network? Relations among Institutions

https://ocw.mit.edu/courses/sloan-school-of-management/15-599-workshop-in-it-collaborative-innovation-networks-fall-2011/lecture-notes/MIT15_599F11_lec04.pdf

Basic concepts of the graph theory

Graph: A graph is a way of specifying relationships among a collection of items

Node: An object, an actor, a point

Computers, telephones

Persons, employees

Companies/business units

Articles/research projects

Neighbors: If the two nodes are connected

Edge

Edge: A link that connects a pair of nodes

Ties, edges, arcs, lines, and links

Types of social relations

Friendship

Acquaintance

Kindship

Advice

Hindrance

Sex

Allow different kind of flows

Messages

Money

Diseases

An edge may contain a direction when a direction is asymmetric

Paths and Cycles

Path: a sequence of nodes with the property that each consecutive pair in the sequence is connected by an edge.

containing not just the nodes but also the sequence of edges linking these nodes

Cycle: A “ring” structured path

A path with at least three edges, in which the first and last nodes are the same, but otherwise all nodes are distinct.

Q1. Why is this redundancy necessary?

Or what is the advantage of a ring structure as opposed to a star structure?

https://www.geeksforgeeks.org/difference-between-star-and-ring-topology/

Roles of Graph

Mathematical models of network structures

Represent how things are either physically or logically linked to one another in a network structure

Connectivity

Connectivity: The state of a graph in which every pair of nodes is connected via a path

The example (Figure 2.6) is built from the collaboration graph at a biological research center.

Nodes: researchers

Edge: co-authored publication

What is the most prominent node? (Centrality)

Who knows the most actors? (degree centrality)

Who has the shortest distance to the other actors?

Who controls knowledge flows?

What happens if this most prominent central node is removed?

Figure 2.6 Collaboration graph

Connected components (or just components)

A subset of the nodes such that: (i) every node in the subset has a path to every other; and (ii) the subset is not part of some larger set with the property that every node can reach every other.

(i) components are internally connected

(ii) a component is a free-standing

Q2. How many connected components do you see in Figure 2.6 in the previous slide and in Figure 2.5 on the right in this slide?

Figure 2.5

Giant Components

A connected component that contains a sign