COMS 4995: Intro Networks & Crowds
Homework #1 – Warming up with Graphs and Randomness
英国CS作业代写价格 We will define a strong tie in the following way: for authors A and B, an edge is a strong tie if A and B share a coauthor.
Why there is three parts in this assignment: Each part fulfills one of the objectives of the class:
- Manipulateconcepts: Getting Familiar with the technical concepts used in class, by reproducing similar Being proficient by manipulating the object to answer some small-size problem.
You are expected to answer this question rigorously, the answer can be quite short as long as it contains all the required argument to justify your answer. 英国CS作业代写价格
- Experience the concepts in real case: Being able to reproduce these concepts on real or synthetic data. Study their properties in real
- Connectthe concepts to real-life: Interpret a problem you find in light of the notions you have Develop some critical eye to determine how the concepts introduced are useful in practice.
How to read this assignment : Exercise levels are indicated as follows
(↣) “elementary”: the answer is not strictly speaking obvious, but it fits in a single sentence, and it is an immediate application of results covered in the lectures.
Use them as a checkpoint: it is strongly advised to go back to your notes if the answer to one of these questions does not come to you in a few minutes.
(↷) “intermediary”: The answer to this question is not an immediate translation of results covered in class, it can be deduced from them with a reasonable effort. 英国CS作业代写价格
Use them as a practice: how far are you from the answer? Do you still feel uncomfortable with some of the notions? which part could you complete quickly?
(↬) “tortuous”: this question either requires an advanced notion, a proof that is long or inventive, or it is still open.
Use them as an inspiration: can you answer any of them? does it bring you to another problem that you can answer or study further? It is recommended to work on this question only AFTER you are done with the rest!
Part A — Manipulating the Concepts 英国CS作业代写价格
Exercise 1: Distance and graph (7 pt)
A photo sharing start-up called ImmediaPrint includes a social feature. It estimates and shows for each account its Jane-Number (named after Jane, founder of the service) that is the number of people in the shortest path from this account to Jane, including Jane but not the source). On the blog post of the service, they mention that all accounts with a path to Jane, the maximum Jane Number is 8.
(↷)Assume that the link between accounts are bidirectional (accounts are reciprocal friends, like inFacebook). What is the diameter of the connected component of the friendship graph that includes Jane? If the answer is not a fixed number, provide the best lower bound and best upper bound you can deduce, with an example where that bound is achieved? 英国CS作业代写价格
(↷) Is the answer to the previous question different if we now assume that the link aredirectional (accounts ”follow” each other, like in Twitter) and a path (used in the definition of Jane number and diameter) must respect the directions of the edges to be valid?
(↷) When a new account is created, the graph changes, including its maximum Jane Number and Diameter. Can the maximum Jane number increase and by how much? Can it decrease and by how much? Same question for the diameter? Justify your answer with an example.
Part B — Experiencing the Concepts 英国CS作业代写价格
Instructions: This part includes programming exercises. In this class, you can pick your favorite programming language to solve programming exercises as long as it’s runnable on our testing environment. We will provide Google coupon for you to be able to run programming language in a standardized manner (more to announce from the TAs):
$ clisp --version GNU CLISP 2.49 (2010-07-07) (built on allspice.buildd [127.0.1.1]) Software: GNU C 4.6.2 $ gcc --version gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3 $ java -version java version "1.6.0_32" OpenJDK Runtime Environment (IcedTea6 1.13.4) (6b32-1.13.4-4ubuntu0.12.04.2) OpenJDK 64-Bit Server VM (build 23.25-b01, mixed mode) $ matlab -r ’ver;exit’ MATLAB Version: 184.108.40.2063 (R2012b) MATLAB License Number: 650045 Operating System: Linux 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 17:37:58 UTC 2013 x86_64 Java Version: Java 1.6.0_17-b04 with Sun Microsystems Inc. Java HotSpot(TM) 64-Bit Server VM mixed mode $ perl --version This is perl 5, version 14, subversion 2 (v5.14.2) built for x86_64-linux-gnu-thread-multi $ python --version Python 2.7.3 $ python3 --version Python 3.2.3 $ R --version R version 2.14.1 (2011-12-22) Copyright (C) 2011 The R Foundation for Statistical Computing ISBN 3-900051-07-0 Platform: x86_64-pc-linux-gnu (64-bit) $ scala -version Scala code runner version 2.11.2 -- Copyright 2002-2013, LAMP/EPFL
Unless specified otherwise, you’re allowed to use any third-party libraries to do graph operations and network analyses,
for example, igraph for C/C++/R, NetworkX for Python, JGraphT for Java, and MatlabBGL for Matlab. However the TAs have very limited support on them.
For each programming exercise, put all files of your solution into a folder named exercise[exercise#],e.g. exercise2.1.Include a README file in the folder to tell the TAs how to compile (if needed) and run your code, and what libraries are used for the question. Makefiles are appreciated. 英国CS作业代写价格
Pack all your folders into a zip file named [UNI] hw[assignment#].zip, e.g. ab123 hw1.zip when you have finished all questions and submit the zip file to CourseWorks.
For example, you will have a zip file with file structure looks like this,
abc_hw1.zip | exercise2.1 | | solution.c | | README | | ... | exercise2.2 | | solution.c | | README | | ... | ...
Exercise 2: Programming warm-up (2pt)
- (↣) Write a program that prints out 42.
- (↣)Write a program that prints out all odd numbers between 50 and 150.
Exercise 3: Graph warm-up (6pt) 英国CS作业代写价格
In this and the next exercise we use a real dataset that shows coauthorship in papers about General Relativity and Quantum Cosmology (sounds complicated!). Thenodes in this social network are authors. The nodes are connected by an edge if the authors are both listed as authors on the same paper. You should download this network here: http://snap.stanford.edu/data/ca- GrQc.html. Download the only file under the “files” section, ca-GrQc.txt.gz. The format .txt.gz is a compression format that can be unzipped with 7-Zip. You can get 7-Zip here: http://www.7-zip.org/. You can assume that this input file, ca-GrQc.txt, is in the working directory when we test your code. 英国CS作业代写价格
Note: You can implement all basic graph algorithms by yourself. But we suggest you get used to a third-party graph library to save your time for this and future exercises.
- (↷)Write a program that reads the network from the input file and prints the maximum degree and minimum degree found in the network.
- (↷)Write a program that reads the network from the input file and prints out the following numbers:
- Percentage of authors with only 1 coauthor.
- Percentage of authors with 10 or fewer coauthors.
- Percentage of authors with 20 or fewer coauthors.
- Percentage of authors with 40 or fewer coauthors.
- Percentage of authors with 80 or fewer coauthors.
Exercise 4: Weak and Strong Ties (7pt)
We will define a strong tie in the following way: for authors A and B, an edge is a strong tie if A and B share a coauthor. That is, there exists an author C such that A and B both have edges to C (A and B have written a paper with C). An edge that is not a strong tie is a weak tie.
- (↷)Strong Tie Function: Write a program that takes two numbers besides the input file, and prints out a boolean value. The two numbers will be the labels of two The output should be True if the two nodes have a strong tie, and it should be Falseif the two nodes don’t share an edge or if the two nodes have a weak tie. You can assume the nodes are in the graph.
- (↷)HowStrong? Write a program that reads the collaboration network from the input file and prints, in order, the number of edges, the number of strong ties, and the number of weak ties. It may be helpful to use the code you wrote for the previous question. 英国CS作业代写价格
- (↷)TheStrength of our Weaknesses: Write a program that reads the collaboration network from the input file, removes all weak ties from the graph (or make a new graph with only the strong ties of the original graph), and prints in order:
- The number of connected componentsoriginally
- The number of connected components without weakties
- Thenumber of nodes in the largest connected component originally.
- The number of nodes in the largest connected component without weak ties.
Part C — Concepts at large Intro Networks and Crowds代写
Exercise 5: Efficiency of social marketing (5 pt)
Imagine you are working for a company that sells online data storage like dropbox, which is cheaper and has better interface than previous products. You product is already well recognized in a small community of early adopters, and now you would like it to get known to the most people. You decide to follow a social recommendation approach:
You start the following promotion: every current active user will be offered 3 invitations that can be forwarded to Facebook friend. When one invitation is accepted by this friend, and she sign up for the product, both users receives 2GB of storage for free. After one week, you see a significant increase of the product adoption through this technique, but it remains moderate. You would like to boost this sale, especially as the competition is quickly getting up to speed.
Your marketing team proposes to you two strategies:
- One called ”grass root” in which, in addition, when two invitations get accepted and these usersare friends, the three of you receives an additional 500MB free storage, to recognize you are a promoting cluster.
- Onecalled ”forward” in which, in the same situation, the 500MB free storage is only given to the originator when two invitations are accepted and these people are not friends inFacebook.
- (↷)Using concept seen in class, which policy would you suggest to use? How would you predict theranking between ”grass root”, ”forward” and the baseline strategy?
- (↷)Your company is also developing an app for online social reviews and recommendations on health, housework and babysitting. You would like your product to be known and plan on offering discount on these products via a similar invitation scheme. Would you provide the same recommendation for which rewarding strategy to use? 英国CS作业代写价格
NB: You do not need to provide a very long answer, a short paragraph is sufficient, but it is important that your answer clearly describes your argument(s) in English without to someone who would not know the concepts in advance. You are welcome to reuse class readings by citing relevant facts.
Exercise 6: Getting to know your online social environment (5 pt)
Choose a number N between 40 and 80. Look at the last N posts on your Facebook wall. For each post, give a point to the friend who who posted it. For each comment or like, give 0.5 points to the friend who posted it. Now, for each of these friends, look at your number of mutual friends.
NB: We recommend you take N sufficiently high so that you see a diversity of people (including some with more points than others). It should overall take no more than 15mn.
NB: We assumed that you can use a Facebook account. If that’s more appropriate you can do the same exercise with RenRen, Google+, Twitter. Please contact us if that creates any difficulty.
- (↷) Do you see any correlation among these two metrics? Can you interpretit?
- (↷) Repeat the same experiment but counting points for the last N posts on your newsfeed, and for the last N messages in your Facebook inbox. Can you comment on any common patterns ordifferences you observe? 英国CS作业代写价格
Please report these two metrics (in an anonymous manner) in a file. The file has one line per friends, with four columns separated by comma: The first columns contains the number of friends in common, The second columns contains how many points for this friend on the wall The third columns contains how many points for this friend on your newsfeed The second columns contains how many points for this friend on your Facebook inbox
For instance, if one of your friend A has three friends in common with you, 5 post in your wall, 1 comment in your newsfeed and 1 message in your inbox, one line in the file will be:
3, 5, 0.5, 1