MIS 373 Week 1 Notes
MIS 373 Week 1 Notes MIS 373
Popular in Social Media Analytics
verified elite notetaker
Popular in Business, management
verified elite notetaker
This 15 page Class Notes was uploaded by Christopher Notetaker on Sunday January 31, 2016. The Class Notes belongs to MIS 373 at University of Texas at Austin taught by Chakrabarti in Spring 2016. Since its upload, it has received 19 views. For similar materials see Social Media Analytics in Business, management at University of Texas at Austin.
Reviews for MIS 373 Week 1 Notes
Can you just teach this course please? lol :)
-Mr. Kianna Bogan
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 01/31/16
The Small World Phenomenon (Ch. 20) 1/27/16 1:42 PM Notes MIS 373 1/27/16 1. It’s a small world a. A couple of interesting facts i. It isn’t just Kevin Bacon ii. It is surprisingly hard to find long paths iii. We’ll ad to this later 2. Outline a. The small world experiments i. Milgram’s experiment and follow-ups b. Basic Search in Networks i. Breadth-first ii. Shortest Path c. Models i. Watts-Strogatz ii. Geographical 3. The Small World Experiments a. Pathways are not quite shorter now a day i. Only 384 chains made it ii. The ones that didn't might actually have required longer paths b. We must account for attrition i. Participation rate = 37% everywhere along the path 1. Each new ‘chain link’ or group, 37% participated and 63% did not participate ii. Longer chains are more likely to get "lost” or deleted along the way iii. If we observe N chains of length 1, there were probably N/0.37 actual chains of length 1 1. For length 2 N / (0.37*0.37) 2. For length 3 N / (0.37*0.37*0.37) c. Median chain length after accounting for attrition i. Chains within your country: 5 ii. Chains across countries: 7 iii. All chains: 7 d. How do you know the next recipient i. Most of the time people pick their next contact of some friend of theirs (mostly from works/school/university) 1. 25% of the time people know these people are weak ties e. Why did you pick this person as the next recipient? i. 1267 total “target” individuals 1. How many of your friends do you use? a. Almost 50% of the time, 35 friends are used 2. Why pick these friends? a. 47% work-related reasons b. 45% geographical reasons c. 7% other (e.g., "they know lots of people") f. But are people making mistakes? i. Asked N=105 people how they would route a letter to any of the others 1. I know this person, or 2. I don’t know him. Instead, I’ll forward the letter to this other person I know ii. Compared these chains against the optimal shortest path iii. They find 1. The mean small world path length (3.23) is 40% longer than the mean of the actual shortest paths (2.30) 2. Model suggest that people makes less than optimal small world choices more than half the time 4. It’s a small world a. Interesting facts i. People can find these paths using only local information 1. Primarily using geographical and work-related reasons 2. But the paths they find are 40% worse than the shortest paths ii. And yet, we expect high clustering coefficient 1. My friends’ friend tend to be my friends too 5. Basic Search in Networks a. How would you find the shortest path in a network? i. 1. What is the shortest path from s to y? From s to everyone else? b. Breadth-first search i. The world is split between 1. “discovered” nodes we know all their friends a. Green 2. “undiscovered” nodes we know nothing about them a. White 3. “frontier” nodes we know some of their friends a. Light Blue ii. Initialization 1. Only person S is on the “frontier” 2. Everyone else is “undiscovered” iii. In each step 1. Expand the frontier a. Each time you expand a node out from the frontier it becomes discovered iv. Step 1 1. v. Step 2 1. vi. Step 3 1. vii. Step 4 1. viii. Step 5 1. ix. Step 6 1. x. Step 7 1. c. Frontier Grows Very Quickly i. If every discovered person brings in 5 new undiscovered friends 1. Step 0: 1 person 2. Step 1: 5 people 3. Step 2: 5*5 = 25 people 4. Step 3: 5*5*5 = 125 people 5. Step 4: 5*5*5*5 = 625 people a. Add all the people up (1+5+25+125+625 = 781) ii. In real-life people have many more friends (~150 people) 1. Many more pairs of people connected by short paths as a result of larger frontiers 6. The Watts-Strogatz “Small World” model a. Parameters i. N = number of nodes ii. k = number of close friends iii. p = rewiring probability b. Idea i. Everyone has lots of close friends and a few “weak ties” to far- off acquaintances ii. Weak ties are random throughout the network in the Watts-Strogatz model c. The Process i. Start with ring of N nodes ii. Connect each node to k nearest iii. For each edge (u, v), with prop p, rewire it to (u, w), where w is chosen uniformly at random d. Starting Graph i. High clustering coefficient ii. But long paths to people on the opposite side 1. e. Ending graph (if we rewired every edge) i. Edges are random ii. There is no clustering iii. The Frontier grows quickly since each discovered node brings in lots of random undiscovered friends shorter paths 1. f. Somewhere in the middle i. Just right 1. g. Summary i. Solid lines: “strong” ties to close neighbors ii. Dashed lines: “weak” ties to far-off acquaintances iii. Strong ties give it high clustering iv. Weak ties give it the short paths 7. How do we incorporate geography model? a. Main idea i. Use the Watts-Strogatz small-world model ii. Except “weak” ties are not random in the Geographic Model 1. They are determined by geographic distance b. c. Decay Rates i. Suppose r = 5 (decay rate) 1. a. Distance = 2 then 1/32 chance of meeting them b. Distance = 3 then 1/243 chance of meeting them 2. If Decay rate is lower then it is more likely that I will be able to meet them through weak acquaintances a. 3. Smaller decay rate a. i. r = 0 1. Weak ties are haphazard ii. r = 4 1. Mostly local connections iii. Weak ties are everywhere when decay rate r=0 ii. There is a trade-off 1. Small r no effect of geography random graph 2. High r no far-off connections can’t have short paths to everyone iii. How do we navigate the grid? 1. Weak ties can “halve” the distance in each step (roughly) a. Use weak ties initially for long-range jumps b. Use strong ties later to home in on target Notes MIS 373 1/25/16 1. Intro a. Finding a job i. Go through a random acquanntience to find your employer 1. Even though you have a bunch of close friends, its your global structure/friends that help you find you jobs a. The new job is not that far away from in the social network ii. People find jobs through weak connections 1. Despite finding jobs through weak connections, the structure of the network is still well connected a. Just 1 or 2 hops from new employer iii. At a higher level 1. Who has what information 2. Who has new information b. Main idea i. “Strong” ties with close friends 1. Connected in deliberate ways ii. “Weak” ties with far-off acquaintances 1. Connected in far off different ways iii. These ties are structurally different 2. Lecture Outline a. Triadic Closure i. Main Idea ii. Measuring via clustering coefficient b. Bridges i. Connection to Triadic Closure ii. Measuring via neighborhood overlap 3. Triadic Closure a. Basic principle i. If two people B and C have a common friend A, then ii. B and C are likely to become friends themselves 1. The B-C edge “closes the triangle” b. Why i. Opportunity ii. B and C are likely to be introduced via A c. Trust i. B trusts C because they have a common friend A d. Incentive i. A feels latent stress if B and C are not friends e. Homophily i. A, B, and C all like the same things f. End effect i. We expect friendships to “close the open edge” ii. Leading to lots of triangles iii. Many more than in a “random” network 1. Social networks close the connections iv. How do we measure triadic closure 1. Clustering coefficient 4. Measuring triadic closure a. What are the properties of a score for triadic closure i. Consider two nodes A and B ii. Suppose they have no common friends 1. Does it matter to triadic closure a. For Triadic Closure there needs to be a common friend iii. Situation 1. No common friends a. No effect on Triadic Closure 2. Three nodes with Two connections a. High chance 3. Three nodes all connected a. Higher chance 4. Mutual friends all connected a. Highest chance iv. Effects 1. No common friends -> no effect 2. With common friend(s) -> closing the triangle is positive 3. More common friends -> stronger effect 5. Clustering coefficient (CC) a. Look only at “V” shapes around each node b. Score depends on weather the ends of the V are friends or not c. CC of A = Number of “Closed” V shapes around A // Number of V shapes around A i. 0 = horrible triadic closure 1. None of my friends know each other ii. 1 = perfect triadic closure 1. Me and my friends are all together d. CC of A = 2 * Number of edges between friends of A // (Number of friends of A) * (Number of friends of A -1) 6. What does triadic closure tell us a. High triadic closure i. My friends all know each other ii. We are all close to each other iii. So we probably have access to the same kinds of information b. My close friends might not have new information i. The job opening they know of, I already knew about them c. Then who can give me new information i. Bridges 7. Bridges a. Bridge i. An edge that is part of every path between the green and red nodes ii. Removing the bridge would disconnect the groups b. However bridges are rare i. Networks are more robust 1. Internet 2. Power grid c. Local Bridge i. Removing a local bridge ii. Doesn’t disconnect the network iii. But increase path lengths 1. Makes the commute harder between two nodes d. Net effect remains the same i. New information arrives via the bridge 8. Bridges and tie strengths a. Bridges bring new information i. Why should a bridge be an acquaintance 1. Strong ties between A and C and A and B makes the likelihood on connection between B and C more likely 2. Social Networks have… a. STRONG TRIADIC CLOSURE i. If A has strong friendships with B and C, then B and C must be connected 3. Suppose A --- B is a bridge a. Can it be a strong tie? i. Yes, but close must exist between all mutual friends of A and B ii. **** If a bridge is the only connection between two communities, then it MUST be a weak tie. It must be an acquaintance **** 1. Otherwise this create interconnected communities and there no longer is a bridge b. “I got the job from an acquaintance, not a friend” i. You heard about the job from bridges, because your close friends are all in a clique, and new information only comes from bridges c. Who are bridges? i. Two close friends of mine are likely to know each other 9. Measuring bridge-ness a. Our earlier intuition i. Removing a bridge pushes communities farther apart 1. In practice, this is too rigid 2. A more robust measure is called neighborhood overlap b. Neighborhood Overlap (Bridges) i. How much overlap is there between friends of A and friends of B? 1. Less overlap means a. Lesser exchange of information b. The communities of A and B are farther apart c. The A----B edge is more bridge-like ii. Jaccard Coefficient (JC) = Number of friends both A and B // Number of friends of either A or B 1. Smaller values -> more bridge-like, less closely connected 10. Tie Strengths on Facebook a. Maintained Relationship i. Simply viewed the other profile b. One-way communications i. Commented or posted c. Mutual communications i. Comments reciprocated d. Analysis i. As we move up the hierarchy of communication less and less friends appear and clusters break down ii. Notes MIS 373 1/20/16 1. Gephi and NodeXL 2. Group Project a. Present using Gephi and NodeXL 3. Group Assignment a. Two Group Assignments i. One group assignment ii. One group assignment with presentation 1. Each group gets $50 a. Find a client that has a Facebook page and build an advertising campaign b. Write up a report and present in front of class, what worked, what did not work 4. Grading a. 1 group assignment (10%) b. 1 group assignment with presentation (20%) c. 1 group project with presentation (25%) d. 1 midterm e. 1 final 5. Material a. Some quantitative material 6. Attendance a. Attend both presentations days for each presentation (four days) 7. Book a. Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by Easley and Kleinberg b. Reading packet online 8.
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'