Transcript What is a social network?

Social Networks and Related Applications
李漢銘
臺灣科技大學資訊工程系
中央研究院資訊科學研究所
1
Outline
•
•
•
•
•
•
•
•
What is a social network
Why social networks
History of social networks
Social network analysis
Related applications
Related resources
Related keywords
References
2
What is a social network?
• A set of dyadic ties, all of the same type, among a set of
actors
– Actors can be persons, organizations, groups
– A tie is an instance of a specific social relationship
3
Why social networks?
• Social network theory produces an alternate view, where the
attributes of individuals are less important than their
relationships and ties with other actors.
• This approach has turned out to be useful for explaining
many real-world phenomena.
4
What can social networks help ?
• How does a kind of fashion become an vogue?
• How does a virus spread and infect people?
• How does a research topic become a hot topic
5
History of social networks
•
1967: Small World Phenomenon (Stanley Milgram)
•
1974: The Strength of Weak Ties (Mark Granovetter)
•
1998: Collective Dynamics of Small-World (Duncan J. Watts and Steven H.
Strogatz)
•
2003: Friendster (An online community that connects people through networks
•
of friends for dating or making new friends )
Now: There are thousands of applications applied to social networks
6
Six Degrees of Separation
• 1967: Small World Phenomenon (Stanley Milgram)
7
First Network Model on the Small-world
Phenomenon
8
Strong Link V.S. Weak Link
Bob
Mary
9
The Strength of Weak Ties
•
1974: The Strength of Weak Ties (Mark Granovetter)
• Strong ties are your family, friends and other people you have strong
bonds to.
• Weak ties are relationships that transcend local relationship boundaries
both socially and geographically.
• Weak ties are more useful than strong ties
10
Friendster
• An online community that connects people through networks
of friends for dating or making new friends
11
Social network analysis
 The shape (Sociogram) of the social network helps to
determine a network's usefulness to its individuals.
 Social network analysis [SNA] is the mapping and measuring
of relationships and flows between people, groups,
organizations, animals, etc.
12
An example of sociogram

.
A is at the centre of two
subgroups of linked nodes
consisting of B, C, and D,
and E and F, respectively. A
also has a connection to G.
A connects to E, but E does
not connect to A.
13
How to do social network analysis
 There are three key principles in social networks.
– Degree
– Density
– Centrality
14
Degree in social networks
15
Density in social networks
16
Centrality in social networks
• Degree Centrality
• Closeness Centrality
• Betweeness Centrality
17
Related applications
•
•
•
•
•
Matthew Effect
Internet Structure
Anti-Spam
Infectious Disease Protection
Motif Finding
18
Matthew Effect
• The rich get richer and the poor get poorer
19
Internet Structure
20
Internet Structure (cont)
• Internet structure is also a small world
• It possess a scale-free topology
• A data transferred from a computer to another computer only
needs four step (Four Degrees of Separation)
21
Anti-Spam
•
Leveraging social networks to fight spam
– Email network has been found with a scale-free topology
– Find the spammer through centrality of social network
22
What is Spam?
• Spam: equivalent of junk mail, unsolicited and undesired advertisements
and bulk email messages.
• Spam Characters
– Distribution
– Sent to Millions
– Can be targeted
• Good Email
– Credibility
– Capability
23
Honey Pot Statistics of Spam
Data Source: http://www.projecthoneypot.org/
24
Social Email Network
• The email network has a low diameter.
– The mean shortest path length in the giant connected component to be 4.95 for a
component size of 56969 nodes
25
Email Scale-free network
• Making use of the high clustering, commercial e-mail
providers can identify communities of users more easily, and
focus marketing more efficiently
26
Personal E-mail Networks
 .
In the largest
component ,
none of nodes
share neighbors
27
Personal E-mail Networks (cont)
 .
Subgraph of a spam component.
Two spammers share many
corecipients (middlenodes). In
this subgraph, no node shares a
neighbor with any of its
neighbors.
 .
Subgraph of a nonspam
component. The shows a higher
incidence of triangle Structures
(neighbors Sharing neighbors)
than the spam subgraph.
28
Infectious Disease Protection
• How does our social network structure influence the
spreading of the disease?
• Whether our knowledge of network help us to fight this kind
of disease?
29
Infectious Disease Protection (cont)
30
Infectious Disease Protection (cont)
• Disease is tipped anytime in a scale-free network
• Coexisting with disease is a new concept in modern disease
protection
• To control the connectors in networks can avoid disease
exploded
31
Motif Finding
• motif
– Subgraphs that have a significantly higher density in the observed
network than in the randomizations of the same.
• Real network vs. 1000 random networks
32
Related resources
• Social networks - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Social_networking
• How to do social network analysis
http://www.orgnet.com/sna.html
• International Network for Social Network Analysis (INSNA)
http://www.sfu.ca/~insna/
• NetLab (provides up-to-date information
on social networks in the broadest sense)
http://www.chass.utoronto.ca/~wellman/netlab
33
Related resources (cont)
[Tools]
• InFlow (Social Network Mapping Software) http://www.orgnet.com/index.html
• NetMiner (SNA Software)
http://www.netminer.com/NetMiner/home_01.jsp
• UCINET (SNA Software)
http://www.analytictech.com/ucinet_5_description.htm
• International Network for Social Network Analysis
http://www.insna.org/INSNA/soft_inf.html
34
Related resources (cont)
• [book] Mark Buchanan,NEXUS:small worlds and the
groundbreaking science of networks. 中文譯本:連結
35
Related resources (cont)
• [book] Duncan J. Watts, SIX DEGREES: The Science of a
Connected Age. 中文譯本:6個人的小世界
36
References
•
•
•
•
[1][web] Jobs and the strength of weak ties,
“http://joi.ito.com/archives/2003/08/16/jobs_and_the_strength_of_weak_ties.html”
[2][web] Social network - Wikipedia, the free encyclopedia,
“http://en.wikipedia.org/wiki/Social_networking”
[3][book] Mark Buchanan,NEXUS:small worlds and the groundbreaking science
of networks
[4] Stanley Milgram, “ Small World Phenomenon , ” Psychology Today,1,6067(1967)
37
References (cont)
• [5]Duncan J. Watts and Steven H. Strogatz, “Collective Dynamics of
Small-World Networks,” Nature 393,440-442(1998)
• [6] P. O. Soykin and V. P. Roychowdhury, “Leveraging social networks to
fight spam,” IEEE Computer, 38(4):61-68, April 2005
• [7] Churchill, E.F.; Halverson, C.A.; “ Guest Editors' Introduction: Social
Networks and Social Networking,” Internet Computing, IEEE Volume
9, Issue 5, Sept.-Oct. 2005 Page(s):14 - 19
38