Transcript Slides - UCF EECS

CNT 5805: Network Science
Fall 2016
Mainak Chatterjee
[email protected]
http://www.eecs.ucf.edu/~mainak/
http://www.eecs.ucf.edu/~mainak/COURSES/fall16/5805
Disclaimers
The slides that I will be using for this
class have been copied from open
sources from the Web. I do not claim
any intellectual property for the
following material.
I thank all other instructors for making the
slides available and making my life easy.
Some real networks
– Social Networks
•
•
•
•
•
Networks of acquaintances
Collaboration networks
– actor networks, co-authorship networks, director networks
Phone-call networks, e-mail networks, IM networks, Bluetooth networks
Sexual networks
Home page/blog networks
– Information Networks
•
•
•
•
Citation network (directed acyclic)
The Web (directed)
Peer-to-Peer networks
Software graphs
– Distribution Networks
•
•
•
•
The Internet (router level, AS level)
Power Grids, Telephone Networks
Airline networks
Transportation Networks (roads, railways, pedestrian traffic)
Some real networks….
– Biological Networks
•
•
•
•
•
•
Protein-Protein Interaction Networks
Gene regulation networks
Gene co-expression networks
Metabolic pathways
The Food Web
Neural Networks
– Economic Networks
•
•
Bank networks
Credit card
– Natural Networks
•
•
•
River networks
Leaf networks
Epidemic
How do networks “look” like?
• Let’s look at some pictures…
• These will give you some idea of what we are
dealing with.
• A word of caution
– When was the data collected
– How was the data collected (methodology)
– Credibility of the experiments
• Nevertheless, the pictures tell a story
Terrorist Network
Actors (https://oracleofbacon.org/)
Links among blogs (2004 presidential)
election)
Product recommendations
Facebook
The “Social Graph” behind Facebook
Technological networks
• Networks built for distribution of commodity
– The Internet
• router level, AS level
–
–
–
–
Power Grids
Airline networks
Telephone networks
Transportation Networks
• roads, railways, pedestrian traffic
PoP-level Internet2 network
The Internet at AS level
Internet as measured by Hal Burch and Bill Cheswick's Internet Mapping Project.
Routers
Power networks
transportation networks: airlines
Source: Northwest Airlines WorldTraveler Magazine
transportation networks: railway maps
Source: TRTA, March 2003 - Tokyo rail map
Biological networks
• Biological systems represented as
networks
–
–
–
–
–
–
Protein-Protein Interaction Networks
Gene regulation networks
Gene co-expression networks
Metabolic pathways
The Food Web
Neural Networks
metabolic
networks
• Citric acid
cycle
• Metabolites
participate in
chemical
reactions
Biochemical pathways (Roche)
Source: Roche Applied Science, http://www.expasy.org/cgi-bin/show_thumbnails.pl
Gene regulatory networks
GRN is a collection of DNA segments in a cell which interact with other indirectly (through
their RNA and protein expression products) and with other substances in the cell, thereby
governing the expressions levels of Messenger RNA (mRMA) and proteins.
•
•
•
humans have 30,000 genes
the complexity is in the interaction of genes
can we predict what result of the inhibition of one gene will be?
Source: http://www.zaik.uni-koeln.de/bioinformatik/regulatorynets.html.en
Protein binding networks
Baker’s yeast S. cerevisiae
(only nuclear proteins shown)
Nematode worm C. elegans
Transcription regulatory networks
Bacterium: E. coli
Single-celled eukaryote:
S. cerevisiae
The Protein Network of Drosophila (a small fly)
CuraGen Corporation
Science, 2003
Metabolic networks
KEGG database: http://www.genome.ad.jp/kegg/kegg2.html
C. elegans neurons
Network of Interacting Pathways (NIP)
381 organisms
A.Mazurie
D.Bonchev
G.A. Buck,
2007
Freshwater food web by Neo Martinez and Richard Williams
Protein interaction networks
Ecological networks
Brain networks
Structural brain connectivity
Economic networks
World-trade networks
Email exchanges in a company
Phone calls in a country
Socio-epidemic networks
Epidemic networks
River networks
Leaf networks
Business ties in bio-tech industry
Nodes:
Companies
Investment
Pharma
Research Labs
Public
Biotechnology
Links:
Collaborations
http://ecclectic.ss.uci.edu/~drwhite/Movie
Financial
R&D
Network Science: Introduction 2012
Enough of pictures
What message did the pictures convey?
Network Science: Introduction 2012
Bottomline….it’s the complexity
We are surrounded by complex systems, from the society (a collection of 7
billion individuals, to communications systems, to neurons in the brain.
All these systems work together in a seamless fashion.
These systems, random looking at first, upon close inspection display endless
signatures of order and self-organization whose quantification, understanding,
prediction and eventually control is the major intellectual challenge.
Network Science: Introduction 2012
THE ROLE OF NETWORKS
Behind each complex system there is a
network (a wiring diagram), that defines the
interactions between the component.
We will never understand complex system
unless we map out and understand the
networks behind them.
Network Science: Introduction 2012
“Complex” networks
• Complex networks are large (in node number)
• Complex networks are sparse (low edge to node
ratio)
• Complex networks are usually dynamic and evolving
• Complex networks can be social, economic, natural,
informational, abstract, ...
Networks in complex systems
• Complex systems
– Large number of components interacting with each other
– All components and/or interactions are different from each other
– Paradigms:
•
•
•
•
104 types of proteins in an organism,
106 routers in the Internet
109 web pages in the WWW
1011 neurons in a human brain
• The simplest property:
– who interacts with whom?
• can be visualized as a network
• Complex networks are just a backbone for complex dynamical
systems
What is Network Science?
• The study of complex systems that can be represented as
(typically dynamic) networks
–
–
–
–
–
–
Society, Economy
Various biological networks (e.g., metabolism)
Brain
WWW, Internet, Transportation nets
Natural networks (global climate system)
Many others
• Relies on:
–
–
–
–
Network data (strong empirical basis)
Network models
Network algorithms
Statistics of network data
Main components of Network Science
• Structural properties of complex networks
– E.g., scale-free, small-world
• Dynamics of networks
• Dynamics on networks
• Dynamics of & on networks (co-evolutionary networks)
• How does structure affect dynamics?
• And how do dynamics affect structure?
The roots of Network Science
•
•
•
•
•
Graph Theory
Statistical Mechanics
Nonlinear Dynamics
Games and Learning
Data mining (“graph mining”) and machine
learning
• Algorithms
• Complexity theory
Applications of Network Science
•
•
•
•
•
•
•
•
•
•
Social networks and social media
Economic networks
Biology
Ecology
Network medicine
Climate science
Brain Science and Neuroscience
Web
Internet and computer networks
.. many others
Why study Network Science now?
The list of chemical reactions that take place in a cell were discovered over a 150 year
period by biochemists and biologists. In the 1990s they were collected in central databases,
offering the first chance to assemble the networks behind a cell.
The list of actors that play in each movie were traditionally scattered in books and
encyclopedias. With the advent of the Internet, these disparate data were assembled into a
central database by imdb.com, mainly to feed the curiosity of movie aficionados. The
database offered the first chance for network scientists to explore the structure of the
affiliation network behind Hollywood.
The detailed list of authors of millions of research papers were traditionally scattered in the
table of content of thousands of journals, but recently the Web of Science, Google Scholar,
and other sites assembled them into comprehensive databases, easing the search for
scientific information.
These databases turned into the first science collaboration maps.
Network Science: Introduction 2012
THE EMERGENCE OF NETWORK SCIENCE
Data Availability:
Universality:
The (urgent) need to
understand complexity:
Movie Actor Network, 1998;
World Wide Web, 1999.
C elegans neural wiring diagram 1990
Citation Network, 1998
Metabolic Network, 2000;
The architecture of networks emerging in various
domains of science, nature, and technology are
more similar to each other than one would have
expected.
During the past decade some of the most important
advances towards understanding complexity were
provided in context of network theory.
Network Science: Introduction 2012
THE CHARACTERISTICS OF NETWORK SCIENCE
Interdisciplinary:
Cell biologists/Computer Scientists/others needs the wiring diagram behind
their system, extracting information from incomplete and noisy data sets.
Empirical, Data driven:
Focus is on data and its utility. Not just mathematical models, but tools to test real data.
The value addition will be judged by the insights it offers.
Quantitative and Mathematical Nature:
Graph theory; organizing principles from statistical physics, control and information
theory, statistics and data mining.
Computational Intensive:
Size of networks giving rise to Big Data. Needs algorithms, database management, data
mining, analytics, software tools.
Network Science: Introduction 2012
Impact of Network Science
Network Science: Introduction 2012
ECONOMIC IMPACT – Business exploiting user data
How come we see
relevant ads when we
browse?
All rely on networks –
connections that we
have with products/
people/things/etc.
Network Science: Introduction 2012
BRAIN RESEARCH
In September 2010 the National Institutes of
Health awarded $40 million to researchers at
Harvard, Washington University in St. Louis,
the University of Minnesota and UCLA, to
develop the technologies that could
systematically map out brain circuits.
The Human Connectome Project (HCP) with
the ambitious goal to construct a map of the
complete structural and functional neural
connections in vivo within and across
individuals.
http://www.humanconnectomeproject.org/overview/
Network Science: Introduction 2012
MOST IMPORTANT
Networks Really Matter
If you were to understand the spread of diseases,
can you do it without networks?
If you were to understand the WWW structure,
searchability, etc, hopeless without invoking the
Web’s topology.
If you want to understand human diseases, it is
hopeless without considering the wiring
diagram of the cell.
Network Science: Introduction 2012
Course Logistics
• CNT 5805: Network Science
• Relatively new: Very few universities offer Network Science
Course Website
The course website:
http://eecs.ucf.edu/~mainak/COURSES/fall16/5805
Linked from my “Teaching” page
Instructor: Mainak Chatterjee
Office: HEC 305
Office hours: Mon/Wed 4:30 – 6:00 PM or by appointments
TA: None
Email: [email protected] (Do NOT use the webcourse email)
Books
A. Barabasi, Network Science
http://barabasi.com/book/network-science/
M.E.J. Newman, Networks: An Introduction, Oxford University Press, 2010.
Not available online.
https://global.oup.com/academic/product/networks-9780199206650
D. Easley and J. Kleinberg, Networks, Crowds and Markets,
Cambridge Univ Press, 2010.
http://www.cs.cornell.edu/home/kleinber/networks-book/
Topics to be covered…this is
what I intend to teach
Graph definitions, paths, components, degree distribution,
clustering, degree correlations, centrality metrics, small-world
property, scale-free property, heavy-tailed degree distributions,
network motifs, Poisson networks, Watts-Strogatz model,
preferential attachment and its variants, applications in
communications and social networks, community identification
and detection algorithms, percolation, vulnerabilities, resilience to
random and targeted attacks, epidemics, immunization strategies,
influence identification, games on networks, strategic network
formation, evolution due to cooperation and non-cooperation on
social networks.
Grading
4 Assignments (4 X 15) = 60 Points
These will be programming assignments and analytical questions.
1 Mid-term exam = 20 points
1 Final exam = 20 points
90+  A
80+  B
70+  C
Plus/minus will be used.
Helps if you know
(I would do all the basics)
• Graph Theory
– Basic definitions and properties
• Probability theory
– Distribution functions (Binomial, Poisson)
• Linear Algebra
– Eigenvalues and eigenvectors
• A bit of differential equations
• Programming knowledge is a must (any language)
http://eecs.ucf.edu/~mainak/COURSES/fall16/5805/
Email: [email protected]