CSL 809 - Special Topics in Complex Networks

Instructor: S. R. S. Iyengar
Time: 8 am to 9:30 am (Mon, Tue, Thu, Fri)

10 am to 1 pm (Sat)
Mailing list:Click here 


Objective

This is a seminar topics course which involves reading some of the state of the art results in complex and social networks. The student is expected to have completed CSL709 with very good hold on the basics of Network Science. The course doesn’t have a prescribed text book. The classes will comprise of seminars given by the students, schedule of which will be announced in the class on weekly basis.

Details of the Classes Conducted

Date and time

Topics covered

Cumulative Hours

1

1st August (10:00 am to 01:00 pm)

Course structure and Overview

3

2

3rd August (08:00 am to 09:30 am)

Weighted Networks

4.5

3

4th August (08:00 am to 09:30 am)

Graph Pipelining

6

4

8th August (09:00 am to 01:00 pm)

Clustering Coefficient Ranking Problem

10

5

12th August (07:00 pm to 09:00 pm)

Problems based on Virality Prediction

12

6

13th August (08:00 am to 12:30 pm)

Virality Prediction Problems continued, Fundamental law of social Networks

16.5

7

14th August (01:00 pm to 03:00 pm)

Knowledge Building and Wikipedia

18.5

8

19th August (08:30 pm to 10:30 pm)

Crowdsourcing and Wikipedia

20.5

9

20th August (08:00 am to 11:00 am)

Multiparty Computation (MPC)

23.5

10

21st August (08:00 am to 10:30 am)

Rank prediction of a node based on Degree Centrality

26

11

22nd August (08:00 am to 12:00 am)

Social Sampling,

Multiparty Computation

30

12

1st September (08:00 am to 11:00 am)

Literature discussion on MPC, Wikipedia and rank prediction

33

13

3rd September (08:00 pm to 11:00 pm)

Knowledge Repository and Q&A

36

14

5th September (09:00 am to 12:00 noon)

Modeling Ecosystem in Knowledge Building

39

15

7th September (08:30 pm to 10:30 pm)

Research Progress discussion

41

16

8th September (08:00 pm to 10:00 pm)

Ranking and Network parameters

43

17

11th September (08:00 pm to 10:00 pm)

Correlation of Degree and Eigenvector Centrality

45

18

17th September (08:00 pm to 10:00 pm)

SMPGC (Secure Multiparty Graph Computation)- Latest Protocol

47

19

18th September (08:00 pm to 10:00 pm)

Pigeonhole Principle as applied to the distribution of centrality measures

49

20

28th September (08:00 pm to 10:00 pm)

Best sampling method for the calculation of global parameters

51

21

29th September (08:00 pm to 10:00 pm)

Effect of addition of a new user to the overall knowledge building process

53

22

30th September (09:00 pm to 11:00 pm)

Perfect distribution of users in categories in knowledge Ecosystem

55

23

2nd October (10:00 am to 11:00 am)

Multiparty computation protocol analysis

56

24

6th October (08:00 am to 09:30 am)

Secure multiparty computation of a graph- an alternate method

57.5

25

12th October (08:30 pm to 10:00 pm)

Commitment schemes (K-anonymity)

59

26

14th October (08:30 pm to 10:00 pm)

Surface curve of Knowledge units wrt the distribution

60.5

27

16th October (03:15 pm to 04:15 pm)

Does Knowledge Repository need Q&A?

61.5

28

19th October (02:00 pm to 03:00 pm)

Evolving Models for Meso-scale Structures

62.5

29

27th October (01:00 pm to 02:30 pm)

MST of a graph with the edge weights being a function of time

64

30

27th October (06:00 pm to 07:30 pm)

Optimally converting a given large matrix into another one with minimum snaps and least error.

65.5

31

4th November (09:00 pm to 11:00 pm)

Evolving models for weighted networks

67.5

32

05th November (08:45 pm to 10:45 pm)

Encouraging non-experts by silencing experts occasionally in KB

69.5

33

17th November (03:00 pm to 05:00 pm)

Edge Classification in Citation Networks

71.5

Syllabus

The syllabus comprises of :

The topics stated above aren’t available in the text book/monograph form, we will mainly be referring to a few research papers, which will soon be updated.

Marks Distribution

Activity

Timeline

Marks

Proposal Report

01 Aug - 03 Aug

5 marks

Literature Report

14 Aug - 16 Aug

10 marks

Analysis Report

01 Sep - 07 Sep

15 marks

Final Manuscript

01 Oct - 07 Oct

70 marks

Grading Scheme (Absolute)

Marks Secured

Grade

[91,100]

10

[81,90]

09

[76,80]

08

[71,75]

07

[66,70]

06

[61,65]

05

[51,60]

04

[0,50]

Fail

References:

  1. A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec, and M. Tiwari, “Global diffusion via cascading invitations: Structure, growth, and homophily,” pp. 66–76, 2015. [Online]. Available: http://dx.doi.org/10.1145/2736277.2741672
  2. J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins, “Microscopic evolution of social networks,” pp. 462–470, 2008
  3. Aral, Sinan, Lev Muchnik, and Arun Sundararajan. ”Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks.” Proceedings of the National Academy of Sciences 106.51 (2009): 21544-21549
  4. Elizabeth Ananat, Shihe Fu, Stephen L. Ross, Race-Specific Agglomeration Economies: Social Distance and the Black-White Wage Gap, NBER Working Paper No. 18933, April 2013
  5. Fronczak, Agata, et al. "Higher order clustering coefficients in Barabási–Albert networks." Physica A: Statistical Mechanics and its Applications 316.1 (2002): 688-694.
  6. Weng, Lilian, Filippo Menczer, and Yong-Yeol Ahn. "Virality prediction and community structure in social networks." Scientific reports 3 (2013).
  7. Cheng, Justin, et al. "Can cascades be predicted?." Proceedings of the 23rd international conference on World wide web. ACM, 2014.
  8. Kitsak, Maksim, et al. "Identification of influential spreaders in complex networks." Nature Physics 6.11 (2010): 888-893.
  9. De Domenico, Manlio, et al. "The anatomy of a scientific rumor." Scientific reports 3 (2013).
  10. Borgatti, Stephen P., and Martin G. Everett. "Models of core/periphery structures." Social networks 21.4 (2000): 375-395.
  11. Hay, Michael, Gerome Miklau, David Jensen, Philipp Weis, and Siddharth Srivastava. "Anonymizing social networks." Computer Science Department Faculty Publication Series (2007): 180.
  12. Goldreich, Oded, Silvio Micali, and Avi Wigderson. "How to play any mental game." In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pp. 218-229. ACM, 1987.
  13. Cramer, Ronald, Ivan Damgard, and Jesper Buus Nielsen. "Secure Multiparty Computation and Secret Sharing-An Information Theoretic Appoach." Book Draft (2012).
  14. Yao, Andrew. "How to generate and exchange secrets." In Foundations of Computer Science, 1986., 27th Annual Symposium on, pp. 162-167. IEEE, 1986.
  15. Brickell, Justin, and Vitaly Shmatikov. "Privacy-preserving graph algorithms in the semi-honest model." In Advances in Cryptology-ASIACRYPT 2005, pp. 236-252. Springer Berlin Heidelberg, 2005.
  16. Qin, Xiangju, Pádraig Cunningham, and Michael Salter-Townshend. "The influence of network structures of Wikipedia discussion pages on the efficiency of WikiProjects." Social Networks 43 (2015): 1-15.
  17. Kittur, Aniket, and Robert E. Kraut. "Harnessing the wisdom of crowds in wikipedia: quality through coordination." Proceedings of the 2008 ACM conference on Computer supported cooperative work. ACM, 2008.
  18. Kimmerle, Joachim, Johannes Moskaliuk, and Ulrike Cress. "Using wikis for learning and knowledge building: Results of an experimental study." Journal of Educational Technology & Society 14.4 (2011): 138-148.
  19. Wang, Gang, et al. "Wisdom in the social crowd: an analysis of quora." Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2013.
  20. Cranshaw, Justin, and Aniket Kittur. "The polymath project: lessons from a successful online collaboration in mathematics." Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2011.
  21. Dasgupta, Anirban, Ravi Kumar, and D. Sivakumar. "Social sampling." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.
  22. Kurant, Maciej, Carter T. Butts, and Athina Markopoulou. "Graph size estimation." arXiv preprint arXiv:1210.0460 (2012).
  23.  Blum, Manuel. "Coin flipping by telephone a protocol for solving impossible problems." ACM SIGACT News 15.1 (1983): 23-27.
  24. Yao, Andrew Chi-Chih. "Protocols for secure computations." FOCS. Vol. 82. 1982.