博客

COMS 4995: Intro Networks & Crowds

Networks & Crowds作业代写 Being able to reproduce these concepts on real or synthetic data. Study their properties in real examples.

Homework #1 – Warming up with Graphs and Randomness

Why there is three parts in this assignment: Each part fulfills one of the objectives of the class:

• Manipulate concepts: Getting Familiar with the technical concepts used in class, by reproducing similar arguments.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.

• Experience the concepts in real case: Being able to reproduce these concepts on real or synthetic data. Study their properties in real examples.

• Connect the concepts to real-life: Interpret a problem you find in light of the notions you have learned. Develop some critical eye to determine how the concepts introduced are useful in practice.  Networks & Crowds作业代写

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.

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  Networks & Crowds作业代写

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.

1. (↷) Assume that the link between accounts are bidirectional (accounts are reciprocal friends, like in Facebook). 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?

2. (↷) Is the answer to the previous question different if we now assume that the link are directional(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?

13. 1 (↷) 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  Networks & Crowds作业代写

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)  Networks & Crowds作业代写

$ matlab -r ’ver;exit’

MATLAB Version: 8.0.0.783 (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.

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)  Networks & Crowds作业代写

1. (↣) Write a program that prints out 42.
2. (↣) Write a program that prints out all odd numbers between 50 and 150.

Exercise 3: Graph warm-up (6pt) In this and the next exercise we use a real dataset that shows coauthorship in papers about General Relativity and Quantum Cosmology (sounds complicated!). The nodes 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/caGrQc.html. Download the only file under the “files” section, ca-GrQc.txt.gz. The format .txt.gz is acompression 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.

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.

1. (↷)Write a program that reads the network from the input file and prints the maximum degree and minimum degree found in the network.

2. (↷)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)  Networks & Crowds作业代写

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.  Networks & Crowds作业代写

1.(↷)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 nodes. The output should be True if the two nodes have a strong tie, and it should be False if 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.

2. (↷)How Strong? 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.

3. (↷)The Strength 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 components originally
• The number of connected components without weak ties
• The number 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  Networks & 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 users are friends, the three of you receives an additional 500MB free storage, to recognize you are a promoting cluster.  Networks & Crowds作业代写

• One called ”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 in Facebook.

1. (↷) Using concept seen in class, which policy would you suggest to use? How would you predict the ranking between ”grass root”, ”forward” and the baseline strategy?

2. (↷) 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?

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)  Networks & Crowds作业代写

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.  Networks & Crowds作业代写

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.

1. (↷) Do you see any correlation among these two metrics? Can you interpret it?
2. (↷) 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 or differences you observe?

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,comment in your newsfeed and 1 message in your inbox, one line in the file will be:

3, 5, 0.5, 1

 

更多代写：Cs Midterm代考  托业代考  Econ温哥华代考  Academic source代写  英文论文写作要点  怎么写毕业论文

合作平台：essay代写 论文代写 写手招聘 英国留学生代写