Social Network Analytics — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

This question paper has two sections A and B. Answer all parts of a question together. (h) Consider a network with edges: (A, B), (A, C), (B, C), (C, D), (D, E), (D, F), (E, F). A community detection method identifies communities as CI = (A, B, C) and C2 - (D, E, F). Compute modularity for the communities C1 and C2. (4) (i) Define the following terms: (4) (iii) K-plex (iv) Degree centrality 2. (a) Explain the three fundamental properties observed in Real World Networks, Also compare real world network with random network. (6) (b) A viral infection spreads in a hostel containing 150 students. Once recovered, students gain temporary immunity and may become susceptible again. Consider the initial conditions and parameters as follows and calculate the following: (3x3-9) Initial Conditions: Total Population: N = 150 Infection Rate (P) = 0.25 Recovery Rate (Y) - 0.10 (i) Calculate rate of change of susceptible population. (Il) Calculate rate of change of infected population. (I1l) Calculate rate of change of recovered population 3. For the network given below (Figure 2), compute the following measures: (5x3=15) degree distribution of the network (il) diameter of the network (iii) local clustering coefficient of node 2 (iv) density of the network (v) closeness centrality of node 3 4. (a) Explain different epidemic models. (6) (b) Calculate purity and rand index of the community distribution as given in Figure 3. Ground truth communities are marked with three different types of shapes and communities predicted are marked with three circles as shown below in the figure. (9) A detected detected detected community 1 community 2 community 3 5. (a) Consider a network with a set of nodes V= (1, 2, 3, 4, 5, 6). Let N(v) denote set of neighbours of vertex v. Given that N(2) - (1, 2, 3, 4, 6) and N(3) - (2, 3, 4, 5). Calculate following similarity measures between the nodes 2 and 3. (6) (i) Jaccard similarity (ii) Common neighbours (lil) Cosine similarity (b) Consider a web network given in Figure 4 with web pages A, B, C and D. Compute pagerank for all web pages for two iterations of the algorithm. Assume damping factor d-0.85. (9) 6. (a) Define K-clique. What is the significance of 'K' in this method? Compare K-clique, K-clan and K-club using an example. (9) (b) Write short note on the following: (4x1.5=6) (i) Strongly connected and weakly connected graph (ii) Betweenness centrality (ili) average path length (iv) Preferential attachment model For the directed network given below (Figure 5), answer the following questions: (i) Find if the network given is strongly connected or weakly connected graph. Justify your ansWer (7) (ii) Calculate betweenness centrality for all nodes. (8)