Transcript Dynamic Structure Mining

Dynamic Structure Mining
Limitations to Traditional SNA
• Social network analysis (SNA) has focused on small, bounded
networks, with 2-3 types of links (such as friendship and advice)
among one type of node (such as people), at one point in time, with
close to perfect information.
• While it is understood, at least in principle how to think about multimodal, multi-plex, dynamic networks, the number of tools, the
interpretation of the measures, and the illustrative studies using such
“higher order” networks are still in their infancy relative to what is
available for simpler networks.
Dynamic Structure Mining
• New nodes may be added to the system and old nodes may be
removed.
• New links may emerge between originally disconnected nodes and
old links may rewire or break.
• Understanding the dynamics and the process of evolution in networks
is of vital practical importance.
• There are two general research questions in this area:
• (a) How to describe the dynamics? and
• (b) How to model and predict the dynamics?
Dynamic Structure Mining
• Recently there have been a number of advances that extend SNA to
the realm of dynamic analysis and multi-color networks.
• There are three key advances:
• 1) the metamatrix,
• 2) treating ties as probabilistic, and
• 3) combining social networks with cognitive science and multi-agent systems.
• These advances result in a dynamic network analysis.
Research on network dynamics
• Mathematics: (purely) random graphs (Erd¨os - Renyi)
• Computer science, theoretical physics:
• study of effects of simple, but not completely random, rules in infinitely growing
networks (e.g., www)
• Sociology: interaction between individuals (friendship, collaboration, sex)
• but also other social actors – organizations, countries.
• Economics: choices by individuals with interdependent payoffs
• game theory – strategic behavior;
• equilibrium, stable networks.
• Biology: interacting species, interacting proteins.
Statistical (inferential) modeling of networks
• allows to test theories about network development,
• about mutually interdependent
• development of networks and behavior;
• allows generalization from empirical data
• to conclusions about populations.
Methodological research program
• how to model network dynamics
• how to model joint networks & behavior dynamics
• how robust are conclusions to misspecification
• work in progress — leads to new perspectives on old questions,
• and to new questions, new wishes for data collection;
• requires painstaking modeling,
• collaboration methodologists – social scientists.
• Misspecification is an issue that has not yet been addressed
sufficiently.
Meta-Matrix
• Focus on people, knowledge/resources, events/tasks and
organizations.
• A core issue for DNA is what are the appropriate metrics for
describing and contrasting dynamic networks.
Meta-Matrix
Probabilistic Ties
• The ties in the meta-matrix are probabilistic.
• Various factors affect the probability, including the observer’s
certainty in the tie and the likelihood that the tie is manifest at that
time.
• Bayesian updating techniques (Dombroski and Carley, 2002),
cognitive inferencing techniques, and models of social and cognitive
change processes (Carley, 2002; Carley, Lee and Krackhardt, 2001) can
be used to estimate the probability and how it changes over time.
Multi-Agent Network Models
• A major problem with traditional SNA is that the people in the
networks are not treated as active adaptive agents capable of taking
action, learning, and altering their networks.
• Multi-agent technology in which the agents use these mechanisms,
learn, take part in events, do tasks to model organizational and social
change.
• The dynamic social network emerges from these actions.
Dynamic Network Theory
• How do networks change?
• What are the basic processes?
Addition and Removal of Relations
• Basic processes are cognitive, social and political in nature.
• Cognitive processes have to do with learning and forgetting, the
changes that occur in ties due to changes in what individuals know.
• Social changes occur when one agent or organization dictates a
change in ties, such as when a manager re-assigns individuals to tasks.
• Political changes are due to legislation that effect organizations and
the over-arching goals.
Change Process for Relations in the MetaMatrix
Tools
• AutoMap, ORA, and Construct
• Data extraction and cleaning can be done for raw text by using a
combination of AutoMap and ORA.
• Analysis and forecasting of change in networks can be accomplished
by using ORA and Construct.
• The tools described here support analysis of networks ranging in size
and scope from a few nodes to 106 nodes per ontology class.
AutoMap
• http://casos.cs.cmu.edu/projects/automap/
• A mixed-initiative system for the extraction of nodes and relations
from raw unformatted texts.
• Content analysis (extraction of concepts and frequencies),
• Semantic network analysis (extraction of network of concepts),
• Dynamic-network analysis (extraction of ontologically cross-classified
nodes and relations)
• Aspects of sentiment analysis.
• AutoMap and ORA are used together in a predefined and optimized
sequence to clean and structure the extracted meta-network data.
• In general, the techniques for extracting and classifying agents,
organizations, and locations are more accurate than those for
knowledge, resources, tasks and beliefs.
• CEMAP is a mixed-initiative system for the extraction of nodes and
relations from semi-structured texts, such as blogs or email.
ORA
• http://casos.cs.cmu.edu/projects/ora/
• A powerful network analysis tool, capable of handling large 106
networks, and supporting meta-network data, geo-spatial network
data, and dynamic network data.
• Relatively unique features include trail, network, and geo-network
visualization, classical and fuzzy grouping algorithms, multi-mode
network assessment.
• ORA can import and export data in a large number of formats
including direct imports for CSV and UCINET and export of images in
png, jpg, pdf, and svg.
Construct
• http://casos.cs.cmu.edu/projects/construct/
• An agent-based dynamic-network model for assessing the coevolution of social and knowledge networks through fundamental
learning, information diffusion and belief dispersion processes.
• Using Construct the impact of various interventions can be assessed
at the individual, group or network level under alternative
communication media environments.
• Construct gains its power for evolving change in the networks by
accounting for the influence of bi-partite networks in constraining the
development of the uni-modal networks.
DyNetML
• http://casos.cs.cmu.edu/projects/dynetml/
• An XML based language for the interchange of relational data.
• DyNetML is used to exchange data between AutoMap and ORA with
AutoMap exporting DyNetML and ORA importing and exporting
DyNetML.