## Description

Question 1

11 There are two quantities to measure the distance between nodes in a network. One is the diameter

12 of the network, which is defined as the maximum distance between any pair of nodes in the network.

13 The other is the average distance, which is defined as the average distance over all pair of nodes in

14 the graph. The two measures in most networks are close to each other. But in some situation they

15 are quite different.

16 1. (15%, 15%) Describe an example of a network where the diameter is more than three times

17 as large as the average distance.

18 2. (10%, 10%) Describe how you could extend your construction to produce networks in which

19 the diameter exceeds the average distance by as large a factor as you would like, i.e., for every

20 positive number c, can you produce a network in which the diameter is more than c times as

21 large as the average distance?

22 Warning: Please carefully check the definitions in the course lecture notes before

23 you work on this problem.

24 Problem 2

25 Implement a naive algorithm in Java to find the diameter of a network based on the Floyd-Warshall

26 algorithm. Use your code to calculate the diameter of an anonymized personal Facebook network

27 described with Personal-May8-Anonymous.gephi, which could be downloaded from Connex → Re28 source.

1

29 1. (20%, 15%) Submit your java source code into connex dropbox.

30 2. (15%, 10%) How many isolated nodes in the network? An isolated node means there is no

31 link between this edge and other nodes.

32 3. (10%, 10%) Clearly, when a network is disconnected, its diameter is infinity. Nevertheless,

33 when you use Gephi to calculate the diameter of Personal-May8-Anonymous.gephi, you will

34 get a number which is obviously not infinity. Find out how the network diameter is calcu35 lated in Gephi. If your code returns a different result compared to Gephi, modify your code

36 accordingly.

37 4. (0%, 15%) Assume that you are allowed to introduce four new edges in the network. Which

38 four new edges would you introduce into the network so that clustering coefficient of your

39 network represented by Personal-May8-Anonymous.gephi is minimized?. In practice, if you

40 want your personal network to be a closely-knit group, the new edges captures the “problems”

41 among your friends that you might want to put efforts to fix.

42 Note: (1) Please treat the network as a directed network. (2) You can build your

43 code over the gephi platform or simply implement your standalone java program. The

44 structure of Personal-May8-Anonymous.gephi is easy to understand if you open the

45 file with a text editor.

46 Problem 3

47 (10%, 10%) Consider the social network represented in the following figure. Suppose that this social

48 network was obtained by observing a group of people at a particular point in time and recording all

49 their friendship relations. Now suppose that we come back at some point in the future and observe

50 it again. According to the theories based on empirical studies of triadic closure in networks, which

51 new edge is most likely to be present? Provide a brief explanation for your answer.

Figure 1: The network in Problem 3

52 Problem 4

53 (20%, 15%) Together with some anthropologists, you are studying a sparely populated region of a

54 rain forest, where 50 farmers live along a 50-mile-long stretch of river. Each farmer lives on a tract

2

55 of land that occupies a 1-mile of the river bank, so their tracts exactly dived up the 50 miles of river

56 bank that they collectively cover. The farmers all know each other, and after interviewing them,

57 you have found that each farmer is friends with all the other farmers that live at most 20 miles

58 from him or her, and is enemies with all the farmers that live more than 20 miles from him or her.

59 Build the signed complete graph corresponding to this social network. If the network structurally

60 balanced or not? Explain your answer.

3