Assignment 4 Going Viral Solution

1. Introduction




Note: Please keep track of the time you spend on this assignment. You will have to give it to us when you submit.




Content —posts, memes, videos— can be shared on social networks. Some content is only posted once. Other content is reposted over and over; it goes viral! A4 uses trees to model how content spreads through a social network. The root of the tree represents the first person to post the content, and the chil-dren of each node represent the people who saw the post by the person represented by that node.




Most of the code you write for A4 involves using recursion to explore a tree. We have supplied you with starter code that simulates the propagation of a shared post as well as a GUI (Graphical User Inter-face) that allows you to set parameters and visualize the results on the screen. But the simulation won’t work until you write recursive methods to process the tree.




Learning objective: Become fluent in using recursion to process data structures such as trees.




Collaboration policy: You may do A4 with one other person. If you are going to work together, as soon as possible —and certainly before you submit the assignment— visit the CMS for the course and form a group. Both people must do something to form a group: one person proposes and the other accepts.




If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping. You should take turns “driving” —using the keyboard and mouse— and “navigating” —reading and re-viewing the code on the screen.




Academic Integrity: With the exception of your CMS-registered partner, you may not look at anyone else's code from this semester or a previous semester, in any form, or show your code to anyone else, in any form. You may not show or give your code to another person in the class.




Getting help : If you don’t know where to start, watch the tutorials about recursion on trees in the Ja-vaHyperText (http://www.cs.cornell.edu/courses/JavaAndDS/recursion/recursionTree.html ) If you still don't know where to start, if you don't understand testing, if you are lost, etc., please SEE SOMEONE IMMEDIATELY—a course instructor, a TA, a consultant, the Piazza for the course. Do not wait.




2. Sharing in Social Networks




Social networks have become a pervasive component of modern life. They connect friends and profes-sional acquaintances, and they are fun! Social networks also have a growing economic impact. Ad-driven social networks are now some of the most valuable companies in the United States. And influential con-tent-drivers can build careers off of a social network presence. Understanding how content spreads through a social network is therefore a priority for economists, sociologists, and psychologists.




In A4, we use an extremely simple model of how content is shared in a social network. We model a social network as a set of cliques —subsets of the network corresponding to social groups in which al-most everyone is friends with almost everyone else— connected by a few links between cliques — friendships between people with different hobbies, backgrounds, or languages. At each time-step, an indi-vidual can choose to share content they have seen with some probability; this probability can be different depending how interesting the original post is and on whether the person they saw it from is in the same

CS2110 Assignment A4. Sharing in Social Networks Due date: on CMS
2
clique or in a different clique. (In the real world, most content is more likely to be shared within a single clique, but not across cliques. Viral content, however, is universally appealing and is equally likely to be shared within a clique or across cliques.) This model provides a real world example of the general tree data structure.




You are not responsible for writing any of the code that implements the simulation of how content spreads through a social network.




The model is initialized with a population of people —1, 2, 10, 50, however many you choose— divided into some number of cliques—1, 2, 5, however many you choose. At the beginning of the simula-tion, a graph is constructed with people as nodes and with random edges between people, indicating they are friends in the social network. You supply a probability indicating that two people in the same clique are friends and a probability that two people in different cliques are friends. A probability of 1 means the two people definitely are friends, a probability of 0 means they definitely are not friends.




When you start the program, you supply three other numbers: the interest score of the content, in 0..10; the probability that a person reposts content they saw from a friend in the same clique; and the probability that a person reposts content they saw from a friend in a different clique. Once you have given this input, the program starts by making one random person post the content and making that person the root of a new repost tree. Initially, that is the only node in the tree.




A series of time-steps follows. In each time-step, a couple different things happen. (1) Each person who has seen the content decides whether to share it with their friends. (2) The interest score of the con-tent —to people who have already seen it— goes down by one. These time steps continue until everyone in the network has either seen the content or has lost interest (the local interest score has gone down to zero). At that time, the results are shown in a GUI on your monitor.













Above is an example of the output in the GUI. At depth 0 (the root) is Joseph; at depth 1 are Michael, John, Charles, Richard, David, Mary, and William. At depth 2 are James and Robert.




Joseph generated the original post; the people at level 1 saw Joseph’s post; the green nodes re-post the post, and James and Robert saw the re-posted post from Michael. Most people were interested enough to re-post the post; only Mary got bored before deciding to re-post it.



To the right in the image above is data that comes from selecting (with your mouse) Michael and then John. It shows: John’s depth, 1; the width at (number of nodes at) that level, 7; John’s parent, number of children, subtree depth, and subtree width; and the shared ancestor of Michael and John.







A run may result in a tree with one node, as shown to the right. This happens when the original post isn’t seen by anyone because the original poster doesn’t have any friends in the social network.



















Installation



Download the A4 assignment zip file from the pinned Piazza note Assignment A4.



Unzip the downloaded file. The folder should contain two folders, data and src; and file



lib.jar.




Create a new Java project (called A4).



Copy-paste all three items in the downloaded folder into the root of the new Java project in Eclipse (i.e. data, lib.jar, and src). When asked how to copy, select “Copy files and folders”, then OK.









When asked what you want to do about the folder already named src there, click “Yes” or “Yes to All”




Right-click the project root and select refresh (F5). Many of the files (as seen below) will have errors on them. This is resolved in steps 6..7.
Add lib.jar to the build path by right clicking lib.jar and selecting Build Path à Add to build path









Add Junit5.jar to the build path as follows: (1) Select the project, right click, and select Build Path - Add libraries. (2) In the window that opens, select JUnit and click Next; in the window that opens, select JUnit 5 and click Finish. (3) Refresh your project root (f5) again.






Running



The executable class of this project is Post.java. To run the project, open Post.java and click run (green button with white arrow) or use menu item Run - Run. You will be prompted for a few seeding values via the console at the bottom of eclipse. These are:




Size of population: how many people to model. A positive integer. A higher number may result in a larger tree.



Number of cliques: the number of cliques in the modeled social network. A higher num-ber may result in a sparser tree.



Probability of connection within a clique: how likely two random people in the same clique are to be friends. (On page 2, we call them neighbors). A float in the range [0,1].



Probability of connection across cliques: how likely two random people in different cliques are to be friends. A float in the range [0,1]. This should probably be lower than the previous number.



Interest of the modeled content: A number in 0..10. The higher the number, the more likely it is to be shared.



Repost probability within a clique: the relative probability that a person shares content they saw from someone else in the same clique. A float in [0,1].



Repost probability across cliques: the relative probability that a person shares content they saw from a friend in a different clique. A float in [0,1]



A nice set of starting values is: (50, 5, 0.8, 0.2, 5, 0.5, 0.1)




If you want to run Post.java repeatedly with the same parameters, you can put them in the program arguments instead of having to type them into the console every time you run the pro-gram. This is done the usual way (Run Configurations… à arguments).




If there is any issue with the arguments provided, either though the console or the program ar-guments (health is less than 0, for example), you will be re-prompted to enter the arguments through the console. Thus, if you have entered arguments in the arguments tab but are still prompted to enter arguments via the console, there may be something wrong with the arguments you entered.




From there, the simulation will start modeling how a post would be shared —starting with a randomly chosen poster and spreading across that person’s connections until everyone who has seen the post has either re-shared it or has become bored.




After the simulation has finished running, the full tree is printed out by calling toStringVer-bose(); then the tree explorer GUI pops up.




Your Tasks



The only file you have to edit is RepostTree.java. Before jumping into the methods, be sure to thoroughly read the javadoc description of the class at the top of the file. in —note that they are marked in blue on the right of the text in Eclipse.




In order to prepare you for writing recursive functions that process trees, we have developed two videos that explain two common patterns for recursive functions on trees. We urge you to watch these two videos before beginning to work on the 7 methods. See link “Recursion” in the navigation bars at the top of the JavaHyperText, or just use this link:




http://www.cs.cornell.edu/courses/JavaAndDS/recursion/recursionTree.html




In order to complete the assignment, complete each method marked with a //TODO comment to the specification listed above the method. There are 7 such methods. You may assume that all preconditions to these methods are respected. In the case that they are not, any behavior (even non-deterministic) is acceptable. It’s best to leave the //TODO comments




Hint: Many of the functions you are asked to write can be written very simply or even trivially (one or two lines) simply by relying on previous functions you have already written or ones that we wrote. The order in which the //TODOs are given (top to bottom) and numbered in Re-postTree.java is the order in which to implement them.




Warning: Every time application Post (i.e. method main in Post.java) is called, a new, random, unrepeatable RepostTree is created, so you cannot debug the methods you are writing using that application. It is best to use a JUnit testing class to test your methods and to run the program only when you know your methods are correct.




Dos and Donts:




Do read all the Javadoc in RepostTree.java very thoroughly. You may choose to read the Javadoc in other files, but it should not be too important. Read the files outside the de-fault package only if you are particularly interested in them —you shouldn’t need to know more than their javadocs in order to complete the assignment.
Do not alter any of the other files given to you. You won’t be able to submit them, so your RepostTree.java must work with unaltered versions of the other files.



Do not change the method signatures of any method in RepostTree. The name and types of parameters should not be changed.



Do not have println statements (which you added to help debug) in your code when you submit. Comment them out or delete them before submitting.



You may add new methods to RepostTree to help complete the required functions (some are only workable with the use of helper methods). Make sure that methods you add are private and have a javadoc comment (/** … */) specification.



Debugging



We give you a JUnit test file RepostTreeTest with the a testing procedure for each function you have to write stubbed in. . Use the same testing practices you learned since A1 and used in A2 and A3. You won’t be submitting the test fil. However, since Post.java is entirely probabilis-tic, a JUnit file is the only way to systematically ensure that your RepostTree is correct.




Debugging your tree method can be difficult. It’s harder than with linked lists, where we were easily able to test all fields using toString(), toStringRev(), and size(). Note that you might find it useful to write helper function(s) that create example trees for you to test on.




Pinned Piazza note A4 FAQs contains some help to get started on testing and debugging.




7. What to submit




Complete the information at the top of file RepostTree.java: your netid(s), the hours and minutes that you spent on this assignment, and any comments you would like to make on this assignment.




Submit file RepostTree.java on the CMS.