diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2014-11-22 21:10:03 -0500 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2014-11-22 21:10:03 -0500 |
| commit | 07f3df73a0109514d2927c43b513fdc3e541780d (patch) | |
| tree | 68834e7cccb75f3be8b89ae81d0fa718e913fc0f | |
| parent | 36eb1fee5492e57368846cbf4e107f1e4cb31589 (diff) | |
| download | fast-seeding-07f3df73a0109514d2927c43b513fdc3e541780d.tar.gz | |
Slides (EconCS 2014-11-21)
| -rw-r--r-- | slides/diag.pdf | bin | 0 -> 7694 bytes | |||
| -rw-r--r-- | slides/diag2.pdf | bin | 0 -> 7690 bytes | |||
| -rw-r--r-- | slides/dist.pdf | bin | 0 -> 106821 bytes | |||
| -rw-r--r-- | slides/graph.pdf | bin | 0 -> 4203 bytes | |||
| -rw-r--r-- | slides/graph.svg | 1164 | ||||
| -rw-r--r-- | slides/graph10.pdf | bin | 0 -> 4246 bytes | |||
| -rw-r--r-- | slides/graph2.pdf | bin | 0 -> 4211 bytes | |||
| -rw-r--r-- | slides/graph3.pdf | bin | 0 -> 4226 bytes | |||
| -rw-r--r-- | slides/graph4.pdf | bin | 0 -> 4225 bytes | |||
| -rw-r--r-- | slides/graph5.pdf | bin | 0 -> 4228 bytes | |||
| -rw-r--r-- | slides/graph6.pdf | bin | 0 -> 4236 bytes | |||
| -rw-r--r-- | slides/graph7.pdf | bin | 0 -> 4236 bytes | |||
| -rw-r--r-- | slides/graph8.pdf | bin | 0 -> 4230 bytes | |||
| -rw-r--r-- | slides/graph9.pdf | bin | 0 -> 4230 bytes | |||
| -rw-r--r-- | slides/hbo_likes.pdf | bin | 0 -> 136434 bytes | |||
| -rwxr-xr-x | slides/main.tex | 359 | ||||
| -rw-r--r-- | slides/para.pdf | bin | 0 -> 105140 bytes | |||
| -rw-r--r-- | slides/perf10.pdf | bin | 0 -> 140612 bytes | |||
| -rw-r--r-- | slides/perf2.pdf | bin | 0 -> 145513 bytes | |||
| -rw-r--r-- | slides/prob.pdf | bin | 0 -> 223953 bytes | |||
| -rw-r--r-- | slides/sampling2.pdf | bin | 0 -> 108493 bytes |
21 files changed, 1523 insertions, 0 deletions
diff --git a/slides/diag.pdf b/slides/diag.pdf Binary files differnew file mode 100644 index 0000000..730e791 --- /dev/null +++ b/slides/diag.pdf diff --git a/slides/diag2.pdf b/slides/diag2.pdf Binary files differnew file mode 100644 index 0000000..58b1b27 --- /dev/null +++ b/slides/diag2.pdf diff --git a/slides/dist.pdf b/slides/dist.pdf Binary files differnew file mode 100644 index 0000000..0ac9c59 --- /dev/null +++ b/slides/dist.pdf diff --git a/slides/graph.pdf b/slides/graph.pdf Binary files differnew file mode 100644 index 0000000..429454c --- /dev/null +++ b/slides/graph.pdf diff --git a/slides/graph.svg b/slides/graph.svg new file mode 100644 index 0000000..b56fd57 --- /dev/null +++ b/slides/graph.svg @@ -0,0 +1,1164 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="744.09448819" + height="1052.3622047" + id="svg2" + version="1.1" + inkscape:version="0.48.5 r10040" + sodipodi:docname="graph.svg"> + <defs + id="defs4" /> + <defs + id="defs3958"> + <style + type="text/css" + id="style3960"> + .node {stroke: #fff; stroke-width: 1.5px;} + .link {stroke: #999; stroke-opacity: .6;} + </style> + </defs> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="3.959798" + inkscape:cx="106.88346" + inkscape:cy="900.70858" + inkscape:document-units="px" + inkscape:current-layer="layer4" + showgrid="false" + inkscape:window-width="1918" + inkscape:window-height="1179" + inkscape:window-x="0" + inkscape:window-y="19" + inkscape:window-maximized="0" /> + <metadata + id="metadata7"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title /> + </cc:Work> + </rdf:RDF> + </metadata> + <g + inkscape:label="Layer 1" + inkscape:groupmode="layer" + id="layer1" + style="display:inline"> + <line + y2="191.21532" + x2="165.68913" + y1="147.65271" + x1="196.97762" + class="link" + id="line3965" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="145.9048" + x2="163.59955" + y1="147.65271" + x1="196.97762" + class="link" + id="line3967" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="184.52026" + x2="185.58359" + y1="147.65271" + x1="196.97762" + class="link" + id="line3969" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="102.64665" + x2="223.1532" + y1="147.65271" + x1="196.97762" + class="link" + id="line3971" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="150.27072" + x2="254.61211" + y1="147.65271" + x1="196.97762" + class="link" + id="line3973" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="173.42325" + x2="202.76532" + y1="147.65271" + x1="196.97762" + class="link" + id="line3977" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="132.8497" + x2="145.43542" + y1="147.65271" + x1="196.97762" + class="link" + id="line3979" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="129.25526" + x2="233.70148" + y1="147.65271" + x1="196.97762" + class="link" + id="line3981" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="171.15874" + x2="241.91922" + y1="147.65271" + x1="196.97762" + class="link" + id="line3983" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="189.27502" + x2="225.18106" + y1="147.65271" + x1="196.97762" + class="link" + id="line3985" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="171.65837" + x2="148.02895" + y1="147.65271" + x1="196.97762" + class="link" + id="line3987" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="209.71901" + x2="193.34146" + y1="147.65271" + x1="196.97762" + class="link" + id="line3989" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="157.21858" + x2="149.8989" + y1="147.65271" + x1="196.97762" + class="link" + id="line3991" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="199.07855" + x2="205.8398" + y1="147.65271" + x1="196.97762" + class="link" + id="line3993" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="104.42422" + x2="154.80557" + y1="147.65271" + x1="196.97762" + class="link" + id="line3995" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="209.71901" + x2="193.34146" + y1="191.21532" + x1="165.68913" + class="link" + id="line3997" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="145.9048" + x2="163.59955" + y1="191.21532" + x1="165.68913" + class="link" + id="line3999" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="184.52026" + x2="185.58359" + y1="191.21532" + x1="165.68913" + class="link" + id="line4001" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="199.07855" + x2="205.8398" + y1="191.21532" + x1="165.68913" + class="link" + id="line4003" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="157.21858" + x2="149.8989" + y1="191.21532" + x1="165.68913" + class="link" + id="line4005" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="171.65837" + x2="148.02895" + y1="191.21532" + x1="165.68913" + class="link" + id="line4009" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="162.91814" + x2="122.04721" + y1="191.21532" + x1="165.68913" + class="link" + id="line4011" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="184.52026" + x2="185.58359" + y1="145.9048" + x1="163.59955" + class="link" + id="line4013" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="173.42325" + x2="202.76532" + y1="145.9048" + x1="163.59955" + class="link" + id="line4017" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="132.8497" + x2="145.43542" + y1="145.9048" + x1="163.59955" + class="link" + id="line4019" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="179.50781" + x2="118.68819" + y1="145.9048" + x1="163.59955" + class="link" + id="line4021" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="96.785667" + x2="136.17899" + y1="145.9048" + x1="163.59955" + class="link" + id="line4023" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="171.65837" + x2="148.02895" + y1="145.9048" + x1="163.59955" + class="link" + id="line4027" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="173.42325" + x2="202.76532" + y1="184.52026" + x1="185.58359" + class="link" + id="line4029" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="189.27502" + x2="225.18106" + y1="184.52026" + x1="185.58359" + class="link" + id="line4031" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="171.65837" + x2="148.02895" + y1="184.52026" + x1="185.58359" + class="link" + id="line4033" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="129.25526" + x2="233.70148" + y1="102.64665" + x1="223.1532" + class="link" + id="line4035" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="120.65272" + x2="250.07664" + y1="102.64665" + x1="223.1532" + class="link" + id="line4037" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="128.65366" + x2="290.30872" + y1="150.27072" + x1="254.61211" + class="link" + id="line4039" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="129.25526" + x2="233.70148" + y1="150.27072" + x1="254.61211" + class="link" + id="line4041" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="120.65272" + x2="250.07664" + y1="150.27072" + x1="254.61211" + class="link" + id="line4043" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="128.65366" + x2="290.30872" + y1="120.65272" + x1="250.07664" + class="link" + id="line4045" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="132.8497" + x1="145.43542" + class="link" + id="line4047" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="162.91814" + x2="122.04721" + y1="132.8497" + x1="145.43542" + class="link" + id="line4049" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="132.8497" + x1="145.43542" + class="link" + id="line4051" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="179.50781" + x1="118.68819" + class="link" + id="line4053" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="171.65837" + x1="148.02895" + class="link" + id="line4055" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="90.854828" + x1="84.005157" + class="link" + id="line4057" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="90.854828" + x1="84.005157" + class="link" + id="line4059" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="150.42894" + x1="70.899872" + class="link" + id="line4061" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="150.42894" + x1="70.899872" + class="link" + id="line4063" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="132.89522" + x1="67.940872" + class="link" + id="line4065" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="132.89522" + x1="67.940872" + class="link" + id="line4067" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="157.21858" + x1="149.8989" + class="link" + id="line4069" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="114.51003" + x1="68.487808" + class="link" + id="line4071" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="114.51003" + x1="68.487808" + class="link" + id="line4073" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="162.66437" + x1="83.616013" + class="link" + id="line4077" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="80.83577" + x1="102.32059" + class="link" + id="line4079" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="53.122932" + x2="133.87769" + y1="80.83577" + x1="102.32059" + class="link" + id="line4081" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="96.785667" + x2="136.17899" + y1="80.83577" + x1="102.32059" + class="link" + id="line4083" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="98.913193" + x2="70.593445" + y1="80.83577" + x1="102.32059" + class="link" + id="line4085" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="80.83577" + x1="102.32059" + class="link" + id="line4087" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="53.122932" + x2="133.87769" + y1="59.222721" + x1="164.13263" + class="link" + id="line4089" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="96.785667" + x2="136.17899" + y1="59.222721" + x1="164.13263" + class="link" + id="line4091" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="104.42422" + x2="154.80557" + y1="59.222721" + x1="164.13263" + class="link" + id="line4093" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="104.42422" + x2="154.80557" + y1="53.122932" + x1="133.87769" + class="link" + id="line4095" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="98.913193" + x2="70.593445" + y1="129.49475" + x1="46.061592" + class="link" + id="line4099" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="96.785667" + x1="136.17899" + class="link" + id="line4101" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="119.55479" + x1="133.19695" + class="link" + id="line4103" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="104.42422" + x2="154.80557" + y1="119.55479" + x1="133.19695" + class="link" + id="line4105" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="98.913193" + x1="70.593445" + class="link" + id="line4107" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="98.913193" + x1="70.593445" + class="link" + id="line4109" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="162.91814" + x1="122.04721" + class="link" + id="line4111" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="162.91814" + x1="122.04721" + class="link" + id="line4113" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="115.08679" + x2="111.55083" + y1="104.42422" + x1="154.80557" + class="link" + id="line4115" + style="stroke:#999999;stroke-opacity:0.6" /> + <line + y2="134.36067" + x2="103.4204" + y1="115.08679" + x1="111.55083" + class="link" + id="line4119" + style="stroke:#999999;stroke-opacity:0.6" /> + </g> + <g + inkscape:groupmode="layer" + id="layer4" + inkscape:label="Layer" + style="display:inline"> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="147.65271" + cx="196.97762" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4121" + sodipodi:cx="196.97762" + sodipodi:cy="147.65271" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4123" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="191.21532" + cx="165.68913" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4125" + sodipodi:cx="165.68913" + sodipodi:cy="191.21532" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4127" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="145.9048" + cx="163.59955" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4129" + sodipodi:cx="163.59955" + sodipodi:cy="145.9048" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4131" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="184.52026" + cx="185.58359" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4133" + sodipodi:cx="185.58359" + sodipodi:cy="184.52026" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4135" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="102.64665" + cx="223.1532" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4137" + sodipodi:cx="223.1532" + sodipodi:cy="102.64665" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4139" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="150.27072" + cx="254.61211" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4141" + sodipodi:cx="254.61211" + sodipodi:cy="150.27072" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4143" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="120.65272" + cx="250.07664" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4145" + sodipodi:cx="250.07664" + sodipodi:cy="120.65272" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4147" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="173.42325" + cx="202.76532" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4149" + sodipodi:cx="202.76532" + sodipodi:cy="173.42325" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4151" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="132.8497" + cx="145.43542" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4153" + sodipodi:cx="145.43542" + sodipodi:cy="132.8497" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4155" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="179.50781" + cx="118.68819" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4157" + sodipodi:cx="118.68819" + sodipodi:cy="179.50781" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4159" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="129.25526" + cx="233.70148" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4161" + sodipodi:cx="233.70148" + sodipodi:cy="129.25526" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4163" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="171.15874" + cx="241.91922" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4165" + sodipodi:cx="241.91922" + sodipodi:cy="171.15874" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4167" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="189.27502" + cx="225.18106" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4169" + sodipodi:cx="225.18106" + sodipodi:cy="189.27502" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4171" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="171.65837" + cx="148.02895" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4173" + sodipodi:cx="148.02895" + sodipodi:cy="171.65837" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4175" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="90.854828" + cx="84.005157" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4177" + sodipodi:cx="84.005157" + sodipodi:cy="90.854828" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4179" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="150.42894" + cx="70.899872" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4181" + sodipodi:cx="70.899872" + sodipodi:cy="150.42894" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4183" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="128.65366" + cx="290.30872" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4185" + sodipodi:cx="290.30872" + sodipodi:cy="128.65366" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4187" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="209.71901" + cx="193.34146" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4189" + sodipodi:cx="193.34146" + sodipodi:cy="209.71901" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4191" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="132.89522" + cx="67.940872" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4193" + sodipodi:cx="67.940872" + sodipodi:cy="132.89522" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4195" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="157.21858" + cx="149.8989" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4197" + sodipodi:cx="149.8989" + sodipodi:cy="157.21858" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4199" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="114.51003" + cx="68.487808" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4201" + sodipodi:cx="68.487808" + sodipodi:cy="114.51003" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4203" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="199.07855" + cx="205.8398" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4205" + sodipodi:cx="205.8398" + sodipodi:cy="199.07855" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4207" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="162.66437" + cx="83.616013" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4209" + sodipodi:cx="83.616013" + sodipodi:cy="162.66437" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4211" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="80.83577" + cx="102.32059" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4213" + sodipodi:cx="102.32059" + sodipodi:cy="80.83577" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4215" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="59.222721" + cx="164.13263" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4217" + sodipodi:cx="164.13263" + sodipodi:cy="59.222721" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4219" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="53.122932" + cx="133.87769" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4221" + sodipodi:cx="133.87769" + sodipodi:cy="53.122932" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4223" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="129.49475" + cx="46.061592" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4225" + sodipodi:cx="46.061592" + sodipodi:cy="129.49475" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4227" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="96.785667" + cx="136.17899" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4229" + sodipodi:cx="136.17899" + sodipodi:cy="96.785667" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4231" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="119.55479" + cx="133.19695" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4233" + sodipodi:cx="133.19695" + sodipodi:cy="119.55479" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4235" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="98.913193" + cx="70.593445" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4237" + sodipodi:cx="70.593445" + sodipodi:cy="98.913193" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4239" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="162.91814" + cx="122.04721" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4241" + sodipodi:cx="122.04721" + sodipodi:cy="162.91814" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4243" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="104.42422" + cx="154.80557" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4245" + sodipodi:cx="154.80557" + sodipodi:cy="104.42422" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4247" /> + </circle> + <circle + cy="115.08679" + cx="111.55083" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4249" + sodipodi:cx="111.55083" + sodipodi:cy="115.08679" + sodipodi:rx="5" + sodipodi:ry="5" + transform="translate(-0.0631351,0.06308418)"> + <title + id="title4251" /> + </circle> + <circle + transform="translate(-1.0205078e-7,-4.9816894e-5)" + cy="134.36067" + cx="103.4204" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + r="5" + class="node" + id="circle4253" + sodipodi:cx="103.4204" + sodipodi:cy="134.36067" + sodipodi:rx="5" + sodipodi:ry="5"> + <title + id="title4255" /> + </circle> + <circle + sodipodi:ry="5" + sodipodi:rx="5" + sodipodi:cy="90.854828" + sodipodi:cx="84.005157" + id="circle5725" + class="node" + r="5" + style="fill:#000000;fill-opacity:1;stroke:#ffffff;stroke-width:1.5px;display:inline" + cx="84.005157" + cy="90.854828" + transform="translate(-1.0205078e-7,-4.9816894e-5)"> + <title + id="title5727" /> + </circle> + </g> +</svg> diff --git a/slides/graph10.pdf b/slides/graph10.pdf Binary files differnew file mode 100644 index 0000000..68fdaae --- /dev/null +++ b/slides/graph10.pdf diff --git a/slides/graph2.pdf b/slides/graph2.pdf Binary files differnew file mode 100644 index 0000000..c7a2f3b --- /dev/null +++ b/slides/graph2.pdf diff --git a/slides/graph3.pdf b/slides/graph3.pdf Binary files differnew file mode 100644 index 0000000..7754700 --- /dev/null +++ b/slides/graph3.pdf diff --git a/slides/graph4.pdf b/slides/graph4.pdf Binary files differnew file mode 100644 index 0000000..b4a75be --- /dev/null +++ b/slides/graph4.pdf diff --git a/slides/graph5.pdf b/slides/graph5.pdf Binary files differnew file mode 100644 index 0000000..a2f8ba9 --- /dev/null +++ b/slides/graph5.pdf diff --git a/slides/graph6.pdf b/slides/graph6.pdf Binary files differnew file mode 100644 index 0000000..d204230 --- /dev/null +++ b/slides/graph6.pdf diff --git a/slides/graph7.pdf b/slides/graph7.pdf Binary files differnew file mode 100644 index 0000000..3072e6a --- /dev/null +++ b/slides/graph7.pdf diff --git a/slides/graph8.pdf b/slides/graph8.pdf Binary files differnew file mode 100644 index 0000000..d98b2cd --- /dev/null +++ b/slides/graph8.pdf diff --git a/slides/graph9.pdf b/slides/graph9.pdf Binary files differnew file mode 100644 index 0000000..c7ac70b --- /dev/null +++ b/slides/graph9.pdf diff --git a/slides/hbo_likes.pdf b/slides/hbo_likes.pdf Binary files differnew file mode 100644 index 0000000..fb3eee7 --- /dev/null +++ b/slides/hbo_likes.pdf diff --git a/slides/main.tex b/slides/main.tex new file mode 100755 index 0000000..ed10070 --- /dev/null +++ b/slides/main.tex @@ -0,0 +1,359 @@ +\documentclass[10pt]{beamer} +\usepackage[utf8x]{inputenc} +\usepackage{amsmath,bbm,verbatim, amsthm} +\usepackage{algpseudocode,algorithm,bbding} +\usepackage{graphicx} +\usepackage{booktabs} +\usepackage{caption} +\usepackage{subcaption} +\DeclareMathOperator*{\argmax}{arg\,max} +\DeclareMathOperator*{\argmin}{arg\,min} +\newcommand{\E}{{\tt E}} + +\title[Harvard EconCS Seminar]{Scalable Methods for Adaptive Seeding\\ +in Social Networks} +\author[Thibaut Horel]{Thibaut Horel \and Yaron Singer} + +%\setbeamercovered{transparent} +\setbeamertemplate{navigation symbols}{} + +\newcommand{\ie}{\emph{i.e.}} +\newcommand{\eg}{\emph{e.g.}} +\newcommand{\etc}{\emph{etc.}} +\newcommand{\etal}{\emph{et al.}} +\newcommand{\reals}{\ensuremath{\mathbb{R}}} +\AtBeginSection[] +{ +\begin{frame}<beamer> +\frametitle{Outline} +\tableofcontents[currentsection] +\end{frame} +} + +\begin{document} + +\maketitle + +\begin{frame}{} + + \begin{center} + \begin{large} + How to leverage social networks to + + \vspace{1em} + + spread information effectively? + \end{large} + \end{center} + +\end{frame} + +\begin{frame}{Influence Maximization} + \begin{center} + \includegraphics<1>[width=0.8\textwidth]{graph.pdf} + \includegraphics<2>[width=0.8\textwidth]{graph2.pdf} + \includegraphics<3->[width=0.8\textwidth]{graph3.pdf} +\end{center} + \begin{center} + Which nodes to actively seed to maximize your influence? \only<4>{[KKT03]} + \end{center} +\end{frame} + +\begin{frame}{Why it doesn't work} + \begin{itemize} + \item You cannot seed anyone in the network + \item Influential users are rare + \end{itemize} + \vspace{1em} + \begin{center} + \includegraphics<1>[width=0.7\textwidth]{graph.pdf} + \includegraphics<2>[width=0.7\textwidth]{graph4.pdf} + \includegraphics<3>[width=0.7\textwidth]{graph5.pdf} + \includegraphics<4>[width=0.7\textwidth]{graph6.pdf} + \end{center} +\end{frame} + +\begin{frame}{Friendship Paradox} + \begin{center} + \begin{large} + ``Your friends have more friends than you do.'' +\end{large} +\end{center} + \vspace{1em} + \only<2->{ + \begin{overprint} + \onslide<2> + \begin{center} + \includegraphics[width=0.7\textwidth]{graph4.pdf} + \end{center} + \onslide<3> + \begin{center} + \includegraphics[width=0.9\textwidth]{dist.pdf} + \end{center} +\end{overprint}} +\end{frame} + +\begin{frame}{Adaptive Seeding} + \begin{itemize} + \item Two-stage process + \item Reach influential nodes through their friends + \end{itemize} + \vspace{1em} + \begin{center} + \includegraphics<1>[width=0.7\textwidth]{graph4.pdf} + \includegraphics<2>[width=0.7\textwidth]{graph7.pdf} + \includegraphics<3>[width=0.7\textwidth]{graph8.pdf} + \includegraphics<4>[width=0.7\textwidth]{graph9.pdf} + \includegraphics<5>[width=0.7\textwidth]{graph10.pdf} + \end{center} + \alert{Question:} Which nodes to select in the first stage? [SS13] +\end{frame} + +\begin{frame}{Outline} +\tableofcontents +\end{frame} + +\section{Adaptive Seeding} + +\begin{frame}{Model} + Influence maximization: +\begin{itemize} + \item graph $(V,E)$ + \item influence function $f:2^V\rightarrow\mathbb{R}_+$ + \item budget $k$ +\end{itemize} +\vspace{1em} +\pause +Plus: +\begin{itemize} + \item core set $X$ + \item for $u\in N(X)$, probability $p_u$ of becoming seedable +\end{itemize} +\end{frame} + +\begin{frame}{Adaptive Seeding} +\begin{itemize} + \item \textbf{First stage:} select $S\subseteq X$ ($|S|\leq k$) + \vspace{1em} + \pause + \item each node $u\in N(S)$ becomes seedable w.p $p_u$ + \\$\Rightarrow$ $R\subseteq N(S)$ subset of seedable nodes + \vspace{1em} + \pause + \item \textbf{Second stage:} maximize $f$ over $R$ with remaining budget ($k-|S|$) +\end{itemize} +\end{frame} + +\begin{frame}{Problem} + \begin{itemize} + \item \textbf{First stage:} select $S\subseteq X$ ($|S|\leq k$) + \vspace{1em} + \pause + \item $p_R$ probability that $R\subseteq N(S)$ becomes seedable: + \vspace{1em} + \pause + \item expected value when selecting $S$ ($|S|\leq k$): + \begin{displaymath} + F(S) = \sum_{R\subseteq N(S)} p_R\; \max_{\substack{T\subseteq R\\ |T|\leq k-|S|}} f(T) + \end{displaymath} + \end{itemize} + \vspace{2em} + \alert{Problem:} Compute $F^* \in \argmax_{|S|\leq k} F(S)$ +\end{frame} + +\begin{frame}{Problem} + \begin{displaymath} + F(S) = \sum_{R\subseteq N(S)} p_R\; \max_{\substack{T\subseteq R\\ |T|\leq k-|S|}} f(T) + \end{displaymath} + + \vspace{1cm} + + \alert{Problem:} Compute $F^* \in \argmax_{|S|\leq k} F(S)$ + + \vspace{1cm} + + Even when the probabilities are all one: + \begin{itemize} + \item NP-hard problem + \item not submodular + \item computing $F(S)$ takes exponential time + \end{itemize} +\vspace{1em} + +\pause +However, $(1-1/e)^2$-approx. algorithm [SS13,\ldots] +\pause +\vspace{1em} + +But\ldots{} running time $O(n^\alpha)$, $\alpha \geq 10$. +\end{frame} + +\begin{frame}{Non-adaptive relaxation} +\begin{itemize} + \item commit in the first stage on the nodes to seed in the second stage + \item randomize +\end{itemize} +\vspace{1em} +\pause + +A non-adaptive solution is a pair $(S, q)$ +\begin{itemize} + \item $S$: nodes selected in the first stage + \item $q$: if node $u\in N(S)$ realizes, select it w.p $q_u$ +\end{itemize} +\vspace{1em} +\pause + +Within budget in expectation: +\begin{displaymath} + |S| + \sum_{u\in N(S)} p_u q_u\leq k +\end{displaymath} +\end{frame} + +\begin{frame}{Non-adaptive problem} +\begin{displaymath} + \begin{split} + \max_{(S,q)}& \sum_{R\subseteq N(S)} (p\cdot q)_R \;f(R)\\ + \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k +\end{split} +\end{displaymath} +\pause +\vspace{1cm} + +Non-adaptive problem: +\begin{itemize} + \item $(1-1/e)$ approx. to the adaptive problem + \item can be solved with approximation $(1-1/e)$ + \pause + \item how to construct adaptive solution from non-adaptive solution? + \begin{displaymath} + (S,q) \mapsto S + \end{displaymath} +\end{itemize} +\end{frame} + +\begin{frame}{Non-adaptive relaxation} + \begin{center} + \includegraphics[height=0.5\textheight]{diag.pdf} + \end{center} +\end{frame} + +\section{Additive Adaptive Seeding} + +\begin{frame}{Additive influence functions} + +From now on: +\begin{displaymath} + f(S) = \sum_{u\in S} w_u +\end{displaymath} + +\vspace{1cm} +$w_u$ is the weight of node $u$: +\begin{itemize} + \item $w_u = \text{deg}(u)$ + \item $w_u$, influence of $u$ in the voter model + \item $w_u$ comes from an external source (e.g. Klout) +\end{itemize} +\end{frame} + +\begin{frame}{Results} + \begin{center} + \includegraphics<1>[height=0.5\textheight]{diag.pdf} + \includegraphics<2>[height=0.5\textheight]{diag2.pdf} + \end{center} +\end{frame} + +\begin{frame}{Non-adaptive Problem (bis)} + \only<1>{ +\begin{displaymath} + \begin{split} + \max_{(S,q)}& \sum_{R\subseteq N(S)} (p\cdot q)_R \;f(R)\\ + \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k +\end{split} +} + + \only<2->{ +\begin{displaymath} + \begin{split} + \max_{(S,q)}& \sum_{u\in N(S)} p_uq_uw_u\\ + \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k +\end{split} +} +\end{displaymath} + +\pause + +\pause +\vspace{1em} +Two algorithms +\begin{itemize} + \item submodular maximization: $\max_q \sum_{u\in N(S)} p_uq_uw_u$ is submodular + \item LP relaxation +\end{itemize} + +\pause +\vspace{1em} +Running time: $O(k^2 n^2)$. +\end{frame} + + +\section{Experimental Results} + +\begin{frame}{Data Collection} + +\begin{table}[t] + \centering + \setlength{\tabcolsep}{3pt} + \begin{tabular}{llrr} + \toprule + Vertical & Page & $m$ & $n$ \\%& $S$ & $F$\\ + \midrule + Charity & Kiva & 978 & 131334 \\%& 134.29 & 1036.26\\ + Travel & Lonely Planet & 753 & 113250 \\%& 150.40 & 898.50\\ + %Public Action & LaManifPourTous & 1041 & 97959 \\%& 94.10 & 722.02\\ + Fashion & GAP & 996 & 115524 \\%& 115.99 & 681.98\\ + Events & Coachella & 826 & 102291 \\%& 123.84 & 870.16\\ + Politics & Green Party & 1044 & 83490 \\%& 79.97 & 1053.25\\ + Technology & Google Nexus & 895 & 137995 \\%& 154.19 & 827.84\\ + News & The New York Times & 894 & 156222 \\%& 174.74 & 1033.94 \\ + %Consumption & Peet's & 776 & 56268 \\%& 72.51 & 520.47\\ + Entertainment & HBO & 828 & 108699 \\%& 131.28 & 924.09\\ + \bottomrule +\end{tabular} +\end{table} +\end{frame} + +\begin{frame}{Friendship paradox (bis)} + \begin{center} + \includegraphics[width=0.8\textwidth]{para.pdf} + \end{center} +\end{frame} + +\begin{frame}{Performance} + \begin{center} + \includegraphics[height=0.8\textheight]{perf10.pdf} + \end{center} +\end{frame} + +\begin{frame}{Performance (bis)} +\begin{figure}[t] + \begin{subfigure}[t]{0.48\textwidth} + \includegraphics[width=\textwidth]{prob.pdf} + \caption{} +\end{subfigure} +\hspace{1pt} +\begin{subfigure}[t]{0.48\textwidth} + \includegraphics[width=\textwidth]{hbo_likes.pdf} + \caption{} + \end{subfigure} +\end{figure} +\end{frame} + +\begin{frame}{Running time} + \begin{center} + \includegraphics[width=\textwidth]{sampling2.pdf} + \end{center} + +\end{frame} + +\end{document} diff --git a/slides/para.pdf b/slides/para.pdf Binary files differnew file mode 100644 index 0000000..eae1c16 --- /dev/null +++ b/slides/para.pdf diff --git a/slides/perf10.pdf b/slides/perf10.pdf Binary files differnew file mode 100644 index 0000000..e8e8de9 --- /dev/null +++ b/slides/perf10.pdf diff --git a/slides/perf2.pdf b/slides/perf2.pdf Binary files differnew file mode 100644 index 0000000..fe08879 --- /dev/null +++ b/slides/perf2.pdf diff --git a/slides/prob.pdf b/slides/prob.pdf Binary files differnew file mode 100644 index 0000000..a4125fe --- /dev/null +++ b/slides/prob.pdf diff --git a/slides/sampling2.pdf b/slides/sampling2.pdf Binary files differnew file mode 100644 index 0000000..4a3924e --- /dev/null +++ b/slides/sampling2.pdf |
