![Algoritmi e Strutture Dati - Heap - Computer Science Divisioncomputerscience.unicam.it/merelli/algoritmi06/[05]heap.pdf · Heap binari: definizione Code di priorit`a Code di max-priorit`a](https://static.fdocumenti.com/doc/165x107/5c4b749d93f3c350ba7bc324/algoritmi-e-strutture-dati-heap-computer-science-div-05heappdf-heap-binari.jpg)
ComputationalSocial Science - DiUniTogoy/materiale/1516/CompSocialSci_Ruffo.pdf ·...
41
03/05/2016 1 Computational Social Science Come si diffonde l'informazione sui social e ARC 2 S Group AppliedResearch on ComputationalComplexSystems Come si diffonde l informazione sui social e sulla rete http://arcs.di.unito.it Giancarlo Ruffo Laboratorio del CdLM in Comunicazione ICT e Media Dipartimento di Informatica Università degli Studi di Torino April 27, 2016 “Data is the new oil”
Transcript of ComputationalSocial Science - DiUniTogoy/materiale/1516/CompSocialSci_Ruffo.pdf ·...
03/05/2016
1
Computational Social Science
Come si diffonde l'informazione sui social e
ARC2S GroupAppliedResearch on ComputationalComplexSystems
Come si diffonde l informazione sui social e sulla rete
http://arcs.di.unito.it
Giancarlo RuffoLaboratorio del CdLM in ComunicazioneICT e Media
Dipartimento di InformaticaUniversità degli Studi di Torino April 27, 2016
“Data is the new oil”
03/05/2016
2
Digitaltracesofhumanbehavior
03/05/2016
3
03/05/2016
4
03/05/2016
5
Come si raccolgono normalmente i dati?
• Questionari
S t i• Svantaggi:
– Limitato dal tipo di domanda (e dal formato della risposta)
– Difficile lavorare sui grandi numeri
– Come si ottengono i dati delle reti “clandestine”?
• Vantaggi:
– Posso controllare il campione scelto su base socio‐demografica
– Raccolgo i dati che mi servono come li voglio
– Metodologicamente ottimali
10
03/05/2016
6
Un esempio
Dati digitali
• I dati possono essere
– già disponibili
– reperibili tramite crawlingintensivo
• Grandi volumi di dati o semplicemente dati che non parlano da soli
• Necessità di tecniche automatiche
12
03/05/2016
7
03/05/2016
8
Dai dati ai modelli alle decisioni
decisioni e policy making
visualizzazioni e HCI
modellazione matematica, sistemi complessi
data mining, machinelearning, naturallanguage
dati
sistemi complessi, scienza delle reti
naturallanguageprocessing, HPC
03/05/2016
9
Dai dati ai modelli alle decisioni
decisioni e policy making
visualizzazioni e HCI
modellazione matematica, sistemi complessi
data mining, machinelearning, naturallanguage
dati
sistemi complessi, scienza delle reti
naturallanguageprocessing, HPC
WHAT IS A NETWORK?
03/05/2016
10
INTERNET
This how you are likely to answer if you are a computer scientist – or just a digital native
domain2
domain1
domain3
router
FROM SADDAM HUSSEIN TO NETWORK THEORY
03/05/2016
11
A SIMPLE STORY (1) The fate of Saddam and network science
Network Science: Introduction
The capture of Saddam Hussein:
shows the strong predictive power of networks.
A SIMPLE STORY (1) The fate of Saddam and network science
Thex
underlies the need to obtain accurate maps of the networks we aim to study; and the often heroic difficulties we encounter during the mapping process.
demonstrates the remarkable stability of these networks: The capture of Hussein was not based on fresh intelligence, but rather on his pre‐invasion social links, unearthed from old photos stacked in his family album.
shows that the choice of network we focus on makes a huge difference: the hierarchical tree that captured the official organization of the Iraqi governmenthierarchical tree, that captured the official organization of the Iraqi government, was of no use when it came to Saddam Hussein's whereabouts.
03/05/2016
12
VULNERABILITY DUE TO INTERCONNECTIVITY
A SIMPLE STORY (2): August 15, 2003 blackout.
Thex
August 14, 2003: 9:29pm EDT20 hours before
August 15, 2003: 9:14pm EDT7 hours after
03/05/2016
13
A SIMPLE STORY (2): August 15, 2003 blackout.
An important theme in network science:
we must understand how network structure affects the robustness of a complex system.
Thex
complex system.
develop quantitative tools to assess the interplay between network structure and the dynamical processes on the networks, and their impact on failures.
We will learn that failures reality failures follow reproducible laws, that can be quantified and even predicted using the tools of network science.
Section 4 NETWORKS AT THE HEART OF COMPLEX SYSTEMS
NETWORKS AT THE HEART OF COMPLEX SYSTEMS
03/05/2016
14
COMPLEX SYSTEMS
Complexity, a scientific theory which asserts that some systems display behavioral phenomena that are
[adj., v. kuhm-pleks, kom-pleks; n. kom-pleks] –adjective 1. composed of many interconnected parts; compound; composite: a complex highway system. 2. characterized by a very complicated or
completely inexplicable by any conventional analysis of the systems’ constituent parts. These phenomena, commonly referred to as emergent behaviour, seem to occur in many complex systems involving living organisms, such as a stock market or the human brain.
S J h L C ti E l di B it icharacterized by a very complicated or involved arrangement of parts, units, etc.: complex machinery. 3. so complicated or intricate as to be hard to understand or deal with: a complex problem.
Source: Dictionary.com
Source: John L. Casti, Encyclopædia Britannica
From the interconnection ofsmallunits
COMPLEX SYSTEMS
28
03/05/2016
15
Toemergentbehavior: complexsystems
COMPLEX SYSTEMS
29
COMPLEX SYSTEMS
30
http://tinyurl.com/o9n9eva
03/05/2016
16
THE ROLE OF NETWORKS
Behind each complex system there is a network, that defines the interactions between the componentbetween the component.
SOCIETY Factoid:
Keith Shepherd's "Sunday Best”. http://baseballart.com/2010/07/shades-of-greatness-a-story-that-needed-to-be-told/
The “Social Graph” behind Facebook
03/05/2016
17
STRUCTURE OF AN ORGANIZATION
: departments
: consultants
: external experts
www.orgnet.com
Brain
Human Brain
BRAIN Factoid:
has between10-100 billion neurons.
03/05/2016
18
The subtle financial networks
Nodes:
BUSINESS TIES IN US BIOTECH-INDUSTRY
Companies
Investment
Pharma
Research Labs
Public
Biotechnology
Links:
http://ecclectic.ss.uci.edu/~drwhite/MovieCollaborations
Financial
R&D
03/05/2016
19
INTERNET
domain2
domain1
router
domain3
Drosophila
Melanogaster
Homo
Sapiens
HUMANS GENES
In the generic networks shown, the points represent the elements of each organism’s genetic network, and the dotted lines show the interactions between them.
03/05/2016
20
HUMANS GENES
Drosophila
Melanogaster
Homo
Sapiens
Complex systems
Made of many non-identical elements connected by diverse interactions.
NETWORK
THE ROLE OF NETWORKS
Behind each system studied in complexity there is an intricate wiring diagram, or a network, that defines the interactions between the component.
We will never understand complex system unless we map y pout and understand the networks behind them.
03/05/2016
21
TWO FORCES HELPED THE EMERGENCE OF NETWORK
SCIENCE
Graph theory: 1735, Euler
THE HISTORY OF NETWORK ANALYSIS
Social Network Research: 1930s, Moreno
Communication networks/internet: 1960s
Ecological Networks: May, 1979.
03/05/2016
22
THE HISTORY OF NETWORK ANALYSIS
The emergence of network maps:
THE EMERGENCE OF NETWORK SCIENCE
Movie Actor Network, 1998;World Wide Web, 1999.C elegans neural wiring diagram 1990Citation Network, 1998Metabolic Network, 2000; PPI network, 2001
03/05/2016
23
The universality of network characteristics:
THE EMERGENCE OF NETWORK SCIENCE
The architecture of networks emerging in various domains of science, nature, and technology are more similar to each other than one would have expected.
THE IMPACT OF NETWORK SCIENCE
03/05/2016
24
GoogleMarket Cap(2010 Jan 1): $189 billion
ECONOMIC IMPACT
Cisco Systemsnetworking gear Market cap (Jan 1, 2919): $112 billion
Facebookmarket cap: $50 billion
www.bizjournals.com/austin/news/2010/11/15/facebooks... - Cached
Reduces InflammationFeverPain
PreventsHeart attackStroke
DRUG DESIGN, METABOLIC ENGINEERING:
COX2
CausesBleedingUlcer
Reduces the risk of Alzheimer's Disease
Reduces the risk of breast cancerovarian cancerscolorectal cancer
03/05/2016
25
DRUG DESIGN, METABOLIC ENGINEERING:
HUMAN DISEASE NETWORK
03/05/2016
26
Dai dati ai modelli alle decisioni
decisioni e policy making
visualizzazioni e HCI
modellazione matematica, sistemi complessi
data mining, machinelearning, naturallanguage
dati
sistemi complessi, scienza delle reti
naturallanguageprocessing, HPC
Solo una formula …
03/05/2016
27
Reti ad invarianza di scala
Predicting the H1N1 pandemic
Thex
https://www.youtube.com/watch?v=ONEOc‐MTm1Q
03/05/2016
28
Real Projected
EPIDEMIC FORECAST Predicting the H1N1 pandemic
ManagementManagement
Barabasi Lab
03/05/2016
29
Barabasi Lab
Barabasi Lab
03/05/2016
30
Section 8
SCIENTIFIC IMPACT
03/05/2016
31
NETWORK SCIENCE The science of the 21st century
•Science:
Special Issue for the 10 year
Complex systems and networks.
anniversary of Barabas i& Albert 1999 paper.
03/05/2016
32
• 1998: Watts-Strogatz paper in the most cited Nature publication from 1998; highlighted by ISI as one of the ten most cited papers in physics in the decade
Original papers:
after its publication.
•1999: Barabasi and Albert paper is the most cited Science paper in 1999; highlighted by ISI as one of the ten most cited papers in physics in the decade after its publication.
•2001: Pastor-Satorras and Vespignani is one of the two most cited papers among the papers published in 2001 by Physical Review Lettersamong the papers published in 2001 by Physical Review Letters.
•2002: Girvan-Newman is the most cited paper in 2002 Proceedings of the National Academy of Sciences.
•The first review of network science by Albert and Barabasi, 2001) is the second most cited paper published in Reviews of Modern Physics, the highest impact factor physics journal, published since 1929. The most cited is Chandaseklar’s 1944 review on solar processes, but it will
REVIEWS:
pbe surpassed by the end of 2012 by Albert et al.
•The SIAM review of Newman on network science is the most cited paper of any SIAM journal.
•BIOLOGY: “Network Biology”, by Barabasi and Oltvai(2004) , is the second most cited paper in the history of Nature Reviews Genetics, the top review journal in
tigenetics.
03/05/2016
33
Disinformazione e
social media
03/05/2016
34
03/05/2016
35
03/05/2016
36
politics
celebrities
spam
astroturf
03/05/2016
37
Possiamo fare qualcosa?
03/05/2016
38
Il nostro modello
Tambuscio & al, RDSM workshop, WWW 2015
N d li i f i
regazione
Numero degli infetti
Segr
Numero dei “creduloni”
03/05/2016
39
03/05/2016
40
QUESTIONS?
Slides ‐ credits
Manyof thelid dh h b d dbslidesusedherehavebeenproducedby
Albert‐LászlóBarabásiwithRoberta Sinatra
www.BarabasiLab.com
80
http://barabasi.com/book/network‐science
03/05/2016
41
THANKSALSOTO…
ARC2S Group
Giancarlo Ruffo Rossano Schifanella Emilio Sulis Marcella Tambuscio Mirko Lai
Luca Maria Aiello André Panisson Martina Deplano
Formermembers
Filippo Menczer Giovanni Luca Ciampaglia Alessandro Flammini Diego Fregolente Ciro Cattuto
Externalcollaborators
![Algoritmi e Strutture Dati - Computer Science Divisioncomputerscience.unicam.it/merelli/algoritmi06/[04]TabelleHash.pdf · Tabelle Algoritmi e Strutture Dati Tabelle Hash Maria Rita](https://static.fdocumenti.com/doc/165x107/5c1b153509d3f2100d8bdfc9/algoritmi-e-strutture-dati-computer-science-div-04tabellehashpdf-tabelle.jpg)
