Transcript Social Network Analysis

Introduction to Social Network Analysis
•
Recent example: www.foaf.sk
•
Historical background: sociology and psychology
•
Defining features
•
Mathematical grounding: algebra + graph theory
•
Recent trends and future work
Marcel Kvassay, Institute of Informatics, Slovak Academy of Sciences
foaf.sk (1) – A View of Slovak Business Registry
cross-check UPC
(closeness = 100%)
December 2009
2
foaf.sk (2) – A View of Slovak Business Registry
Surprise No.1
closeness = 81%
Why not symmetrical?
How is it defined?
December 2009
3
foaf.sk (3) – A View of Slovak Business Registry
Visualization of Mr. Rusko’s network shows him to be 3 steps away from UPC.
December 2009
4
foaf.sk (4) – A View of Slovak Business Registry
Visualization of the UPC network shows Mr. Rusko to be 3 steps away, too.
December 2009
5
foaf.sk (5) – A View of Slovak Business Registry
Surprise No. 2: Mr. Rusko’s history overview in foaf.sk does not show UPC at all.
So how could he have been 100% close to UPC?
December 2009
6
foaf.sk (6) – Deeper Issues
See, Interpret, Adjust:
•
The “social network” kind of interface is great at making people see things…
•
… but to be useful, it must help them interpret what they see:
– Users must know the definitions
– Results must be mutually consistent …
– … and not polluted by too much data
•
Users also need to adjust the process (include/exclude certain types of data or
steps in the computation):
– Configurability of the process
Example: Of all the various relations between individuals and companies (owner, CEO,
member of the board, stock-holder, etc.), users should be able to choose which ones to
include (only owner links, for instance).
December 2009
7
foaf.sk (7) – Lessons Learnt
Social Network Analysis (SNA)
– is more than a graphical interface
– requires an in-depth knowledge of the subject
area that is to be explored through SNA
Users and implementers can benefit from
learning more about the history of SNA, and
how its founders applied it.
December 2009
8
Sociology and psychology
Sociology
(focus: society)
Social psychology
(focus: small groups)
SP2
Psychology
(focus: the individual)
SP1
Psychology: study of mental functions (perception, cognition, attention, emotion,
motivation, personality, etc.), and their role in individual and social behavior
Sociology: analysis of human social activity, from the micro level (agency and
interaction) to the macro level (systems and social structures)
Two distinct varieties of social psychology at their intersection:
SP1 (in psychology) focuses on the individual: how the thoughts, feelings, and
behaviors of individuals are influenced by other people
SP2 (sociology) is more “inter-individual” (group dynamics, crowd-phenomena…),
usually in the context of larger social structures (race, class, gender, etc.)
December 2009
9
Beginnings of social science
Utilitarian theorists (Hobbes, Locke), classical Economists
(Smith, Ricardo, Mill), Liberal philosophers (Herbert Spencer)
Individualism: (1) society exists for the benefit of independent individuals;
(2) social phenomena are to be understood in terms of independent actions and
properties of individuals pursuing private ends. [Theory of social contract]
Beginnings of social science (as different from social thought):
Karl Marx (1818-83) emphasized “the massive fact of the structuring of
interests” and postulated the objective existence (as well as the crucial role)
of social classes and class struggle.
Beginnings of sociology:
Auguste Comte: unit of analysis
= FAMILY (not individual)
Classical Sociologists (Durkheim, Weber, …): It is not enough to postulate
the collective formations, their existence and emergence need to be explained.
adapted from (Parsons, 1932, 1949) and (Freeman, 2004)
December 2009
10
Classical Tradition in Sociology
Max Weber (1864-1920): Social action as a foundation concept. Social life
consists of complexes of social action that can be studied by analytic procedures.
George Herbert Mead (1863-1931): Social behavioral foundations of human
action systems. Mind, self, symbols, and institutions co-emerge in evolution.
Georg Simmel (1858-1918): Interaction concept as essential for sociology.
Society is interaction among individuals. The subject matter of formal sociology
consists of forms of interaction, a kind of geometry of the social world.
Émile Durkheim (1858-1917): Integration as a fundamental problem.
Neural networks are to psychic facts as social networks are to social facts. Social
facts (as well as the emergent social integration) require sociological explanation.
Vilfredo Pareto (1848-1923): System concept as a key tool for theorizing.
Scientific theory is analytical and abstract; it constructs idealized models.
adapted from (Fararo, 2000)
December 2009
11
Three Components of Sociological Theory
Pure methodology:
how shall we best find out
what the society really is?
Objective history:
What the society
was in the past,
and what it will be
in the future.
Subjective
aspirations:
What should the
society be? What
shall we try to
make it into?
Adapted from (Fararo, 2000)
December 2009
12
SNA precursors: Small-scale research
Often a field-study (and reaction to speculative “grand theories”):
•
Pierre Huber – studies of the dominance behavior of bumble-bees (1802),
and of ants (1810). These kinds of studies still continue today.
•
Lewis Henry Morgan – ethnography of the Iroquois (1851) – the earliest
example of systematic data collection on humans.
•
Alexander Macfarlane – formal algebraic model of kinship (1883):
Basic relation:
Then:
•
c = “is child of”
c-1 = parent;
cc or c2 = grandchild
Bienaymé-Galton-Watson process – disappearance of family names
adapted from (Freeman, 2004)
December 2009
13
Bienaymé-Galton-Watson process
Sir Francis Galton, on the
right, 1909, with Karl Pearson
from (Freeman, 2004)
December 2009
14
Social Network Analysis: defining features
Psychology
Sociology
SNA+
SNA
SP1
SP2
Social Network Analysis (SNA) is characterized by
1.
2.
3.
4.
Structural intuition (i.e. patterning of social ties influences actors);
Collection of systematic empirical data;
Use of rigorous mathematical and computational models;
Graphic imagery.
(adapted from Freeman, 2004)
Birth (1930s): J.L. Moreno (sociometry)
W. Lloyd Warner, Elton Mayo (“Harvard group”)
Established (1970s):
Harrison C. White (“Harvard renaissance”)
Expansion – SNA+ (1990s):
December 2009
large-scale “real” social networks, Internet
15
Sociometry, 1930s - example
Sociogram (signed digraph) of a football team (from Freeman, 2004)
December 2009
16
Harvard group, 1930s – example 1
Structure of friendships in an industrial setting (from Freeman, 2004)
December 2009
17
Harvard group, 1930s – example 2
Reported (informal) cliques in an industrial setting (from Freeman, 2004)
December 2009
18
The group of Alex Bavelas, MIT, 1948-50
•
Study of the effects (on efficiency, morale, etc.) of a single individual’s
dominance over the organization’s communication network
•
Formal definitions of “clique” and “centrality”
adapted from (Freeman, 2004)
December 2009
19
Postclassical Theoretical Sociology
•
Talcott Parsons – 1st Phase: The Structure of Social Action (1937)
(a prelude to an analytical theory of social action systems).
Basic structural concept = means-end chain (a series of interconnected
actions, a kind of path through an action space).
•
Talcott Parsons – 2nd Phase: The Social System (1951)
(The theory became structural-functional with focus on mechanisms of
socialization and social control).
•
G.C. Homans – 1st Phase: The Human Group (1950)
(The problem = explain the emergence, maintenance & change of systems of
social relationships among persons via rigorous dynamical system analysis).
•
G.C. Homans – 2nd Phase:
(From a theory as modeled on a system of differential equations, he moved to
theory as a system of propositions forming a deductive system. The behavioral
principles function as the covering laws.)
adapted from (Fararo, 2000)
December 2009
20
Postclassical Theoretical Sociology (2)
•
G.C. Homans – 2nd Phase:
reduction of sociology to
principles of behavioral
psychology
adapted from (Fararo, 2000)
December 2009
21
Other contributions (1940s and 1950s)
•
Cartwright and Harary: formal statement (in signed graphs) of the
notion of cognitive balance proposed by the psychologist Heider.
•
Leo Katz: new probability-based formal models.
•
Torsten Hägerstrand, Sweden: Monte Carlo simulation of the spread of
(agricultural) innovations across space and time using the distance factor
derived from marriage statistics.
•
Nicolas Rashevsky: mathematical biology, mathematical sociology.
One of his early students, Walter Pitts, is generally recognized as the founder
of neural net modeling. This group also worked on the interpersonal process
underlying the diffusion of information and on the formal models of
dominance hierarchies.
•
Pool and Kochen (cca 1958): the notion of the small world.
Milgram (1967) drew on their work in his dissertation (small-world experiment).
adapted from (Freeman, 2004)
December 2009
22
Other contributions (1960s)
•
Anatol Rapoport (1961): random and biased nets (preferential attachment).
•
Claude Flament (Sorbonne, France) (1963): Applications of Graph Theory
to Group Structure (Integrated approach to communication and structural
balance with applications on work groups, political blocs and kinship structures)
•
Harary, Norman, Cartwright (1965):
Structural Models: An Introduction to the Theory of Directed Graphs
•
James A. Davis (1967) generalized Heider’s (1946) idea of balance from a
cognitive to a social structural context
• By the end of 1960s, no version of network analysis was universally recognized,
but people were “ready to embrace a structural paradigm.”
• Mark S. Granovetter (1973) “The strength of weak ties” (bridges / triads)
adapted from (Freeman, 2004)
December 2009
23
Notion of cognitive / structural balance
Crucial role of triads
picture taken from (Coleman, 1988, “Free riders and zealots”)
for Granovetter, 1b is a forbidden triad (implies the third link)
December 2009
24
Harvard renaissance: Harrison C. White (1)
Blocks in the bank wiring room (1976):
December 2009
25
Harvard renaissance: Harrison C. White (2)
4 (out of 10 distinct)
elementary blockmodels:
G/S = passive block with
undiscriminating active
block
H/T = shared perceptions
E/F = center versus periphery
(“hangers-on”)
V/W = Idealized hierarchy
(deference)
December 2009
26
Harvard renaissance: Harrison C. White (3)
•
Management Conflict and Sociometric Structure (1961)
Inferred feelings (p = liking, n=dislike, 1=frequent contact)
[raw data also had a=ambivalent, o=neutral]
“Qualitative addition”
Algebraic Clique detection
Square matrices:
R = feelings (p, n, a, o)
M = contact (1, 0)
T = resulting clique structure
(diagonal to be ignored)
alpha = filtering multiplication
December 2009
27
Trends (1): Computational Sociology
(Context: New tools vs. creative use of the old ones)
Mathematical sociology:
•
Posit simple principles that in combination create complex but regular
patterns (algebraic, stochastic and other methods)…
Computational sociology:
•
Computer simulations based on interacting agents
Could be classed as a “new math” designed to capture the “organized
complexity” (where the patterns cannot be analytically deduced)
•
Generative approach: provide micro-specifications (initial agents,
environments, rules) sufficient to generate the macrostructure of interest.
Links to data farming …
•
Still there is an anti-mathematical bias: be formally adequate but relevant
Adapted from (Skvoretz, 2000)
December 2009
28
Trends (2): “The Spirit of Unification”
4 types of the social
structure representation:
Unification of mid-range theories:
biased nets = Network + distribution
(Fararo, 1989)
<abstract algebra> = grammar + net
(Fararo and Doreian, 1984)
game + net + distribution:
(Bienenstock and Bonacich 1992)
(Peter Abell, 1989)
December 2009
Adapted from (Fararo, 2000)
29
Trends (3): Social Networks and Semantics
SNA’05: Semantic Network Analysis Workshop (4th International
Semantic Web Conference, ISWC 2005, Galway, Ireland)
•
Recent shift in the aims of Computer Science and Artificial Intelligence …
replacing humans
supporting humans
•
sparked the interest in collaborative structures & communities …
•
that have long been studied by Social Network Analysis.
•
Introduction of semantics into SNA allows for richer analysis schemes.
Example research topics:
Emergent semantics in communities; Inferred trust values; Generalized preferential
attachment; Social semantics of FOAF networks; Semantic interoperability in social
networks; Unified models of social networks and semantics.
December 2009
30
SNA in COMMIUS: promising, not yet mature
•
Could be taken as a simple and
configurable neural network:
inputs >>> via >>> outputs
•
Spreading activation needs
exactly two steps
Future work:
Objects
December 2009
email
•
Flat model: no ontologies
•
no positive/negative distinction
•
No subcategory distinction
(e.g. search for partner: time,
cost, quality, compatibility)
•
No spam filter (distortion)
•
Pure quantitative correlation:
(“bridges” as most relevant)
from/to
31
BIBLIOGRAPHY
Coleman, James S. 1988. “Free Riders and Zealots: The Role of Social Networks.”
Sociological Theory, Vol. 6, No. 1.
Fararo, Thomas J. 2001. “Theoretical Sociology in the 20th Century.”
Journal of Social Structure, Vol. 2.
(URL: http://www.cmu.edu/joss/content/articles/volume2/Fararo.html)
Freeman, Linton. 2006. The Development of Social Network Analysis.
Vancouver: Empirical Press. (URL: http://aris.ss.uci.edu/~lin/book.pdf)
Parsons, Talcott. 1932. “Economics and Sociology: Marshall in Relation to the
Thought of His Time.” The Quarterly Journal of Economics, Vol. 46, No. 2.
Parsons, Talcott. 1949. “Social Classes and Class Conflict in the Light of Recent
Sociological Theory.” The American Economic Review, Vol. 39, No. 3.
Skvoretz, John. 2000. “Looking Backwards into the Future: Mathematical Sociology
Then and Now.” Sociological Theory, Vol. 18, No. 3.
White, Harrison C. 1961. Management Conflict and Sociometric Structure.” The
American Journal of Sociology, Vol. 67, No. 2.
White, Harrison C., Scott A. Boorman and Ronald L. Breiger. 1976. “Social Structure
from Multiple Networks. I. Blockmodels of Roles and Positions.” The American
Journal of Sociology, Vol. 81, No. 4.
December 2009
32