Facebook's TAO

TAO: Facebook’s Distributed Data Store for the Social Graph
We introduce a simple data model and API tailored for serving the social graph, and TAO, an implementation of this model. TAO is a geographically distributed data store that provides efficient and timely access to the social graph for Facebook’s demanding workload using a fixed set of queries. It is deployed at Facebook, replacing memcache for many data types that fit its model. The system runs on thousands of machines, is widely distributed, and provides access to many petabytes of data. TAO can process a billion reads and millions of writes each second
https://www.usenix.org/conference/atc13/tao-facebook%E2%80%99s-distributed-data-store-social-graph

Graph Applications in Cybersecurity Domain

Large Scale Graph Analytics and Randomized Algorithms for Applications
in Cybersecurity
http://dl.acm.org/citation.cfm?id=2459984
http://www.graphanalysis.org/SIAM-CSE13/02_Johnson.pdf

A network hacking attack in which hackers repeatedly steal password hashes and move through a computer network with the goal of reaching a computer with high level administrative privileges is known as a pass-the-hash attack. In this paper we apply graph coarsening on graphs obtained from computer network data for the purpose of (a) detecting hackers using this attack and (b) assessing the risk level of the network's current state. We repeatedly contract edges (obtaining a graph minor), which preserves the existence of paths in the graph, and take powers of the adjacency matrix to count the paths. This allows us to detect the existence of paths as well as find paths that have high risk of being exploited by adversaries.


W. Eberle and L. Holder. Applying graph-based anomaly detection approaches to the discovery of insider threats. In IEEE International Conference on Intelligence and Security Informatics (ISI), 2009.

D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. In Proc. 40th Annual ACM Symposium on Theory of Computing, 2008.


S. Jajodia, S. Noel, and B. O'Berry. Topological analysis of network attack vulnerability. In V. Kumar, J. Srivastava, and A. Lazarevic, editors, Managing Cyber Threats: Issues, Approaches and Challenges, pages 248--266. Kluwer Academic Publisher, 2005.


http://vulcan.ee.iastate.edu/~gmani/personal/papers/journals/IEEE-PS-08.pdf

Measuring Security Risk of Networks Using Attack Graphs
http://users.encs.concordia.ca/~wang/papers/ijngc10.pdf

U Kang's Research Goal Statement
http://www.cs.cmu.edu/~ukang/ukang-research.pdf

http://www.eecs.wsu.edu/~holder/pubs/EberleCATCH09.pdf

Cassovary: Twitter's Graph Processing Library

http://engineering.twitter.com/2012/03/cassovary-big-graph-processing-library.html

Open Data Initiative

Open Data Initiative
http://www.theodi.org/

Sociable Physics

http://sociablephysics.wordpress.com/

Open Data

Nokia Mobile Data Challenge
http://research.nokia.com/page/12000
http://publications.idiap.ch/downloads/papers/2012/Laurila_MDC_2012.pdf

Orange D4D Challenge
http://www.d4d.orange.com/

Open Data - Nottingham
http://www.opendatanottingham.org.uk/catalogue.aspx

Kenya Open Data
http://www.princeton.edu/successfulsocieties/content/data/policy_note/PN_id206/Policy_Note_ID206.pdf

Dublinked
http://www.dublinked.ie/

FutureICT
http://www.futurict.eu/

Location Prediction from Tweets

http://infolab.cse.tamu.edu/static/papers/cikm1184c-cheng.pdf
http://www.hpl.hp.com/research/scl/papers/socialmedia/socialmedia.pdf
http://doras.dcu.ie/16754/1/nohare_paper.pdf

Interactive Hybrid Simulation of Large Traffic

Interactive Hybrid Simulation of Large Traffic

Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation

Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation
http://www.cs.cmu.edu/~ukang/papers/HeigenPAKDD2011.pdf

Ogata-kun's work should refer the above effort ...

Origin-Destination Data Generation

Deriving origin–destination data from a mobile phone network
http://www.esi2.us.es/GT/docs/iet_art1.pdf

DYNAMIC ORIGIN-DESTINATION MATRIX ESTIMATION AND PREDICTION FOR REAL- TIME TRAFFIC MANAGEMENT SYSTEMS
http://trid.trb.org/view.aspx?id=640422

Time-Varying Network Tomography : Router Link Data
ftp://cs.bell-labs.com/cm/stat/doc/NetTomography.pdf

Development of Revised Methodology for Collecting Origin-Destination Data
http://www.dot.state.fl.us/research-center/Completed_Proj/Summary_PL/FDOT_BD544_30_rpt.pdf


Real-Time Estimation of Origin-Destination Matrices with Partial Trajectories from Electronic Toll Collection Tag Data

http://pubsindex.trb.org/view.aspx?id=775157


Dynamic Origin–Destination Demand Estimation　Using Automatic Vehicle Identification Data

http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1603556&userType=inst

Distributed Approach for Estimation of Dynamic Origin—Destination Demand

http://trb.metapress.com/content/96400l51428r4737/

デビッド・マキャンドレス 「データビジュアライゼーションの美」

http://www.ted.com/talks/lang/ja/david_mccandless_the_beauty_of_data_visualization.html

Gephi

Gephi (http://gephi.org/)


Gephi is an open-source and multiplatform software distributed under the dual license CDDL 1.0 and GNU General Public License v3.

Layout algorithms give the shape to the graph. Gephi provides state-of-the-art algorithms layout algorithms, both for efficiency and quality. The Layout palette allows user to change layout settings while running, and therefore dramatically increase user feedback and experience: Force-based algorithms or Multi-level algorithms (graph coarsening). 

Video demonstration : 

https://gephi.org/videos/

Time-evolving network visualization

Hashikawa-kun will be working on the time-evolving twitter network since 2006.

The reference demo might be as follows :

Egyptian Revolution on Twitter
https://gephi.org/tag/dynamics/

http://www.youtube.com/watch?v=9guRNGiNBAg
http://www.youtube.com/watch?v=KKNxulf7RNg&feature=relmfu
http://www.youtube.com/watch?v=Hos4m3iO108&feature=related
http://www.youtube.com/watch?v=hI-7wteRv7E
http://computationallegalstudies.com/2010/01/06/the-time-evolving-structure-of-the-gawaher-islamic-forum-as-experienced-by-umar-farouk-abdulmutallab-the-christmas-day-bomber/
http://www.youtube.com/watch?v=a7uTKwbsFtg&feature=related


Not relevant but still interesting visualization:
http://www.evolutionoftheweb.com/?hl=ja#/growth/day

Research on Microblog services / Twitter

What is Twitter, a Social Network or a News Media?http://an.kaist.ac.kr/~haewoon/papers/2010-www-twitter.pdf

A geographic study of tie strength in social media
http://dl.acm.org/citation.cfm?id=2063959&CFID=100588297&CFTOKEN=89581781

Outtweeting the Twitterers - Predicting Information Cascades in Microblogs
http://static.usenix.org/event/wosn10/tech/full_papers/Galuba.pdf

Why Rumors Spread Fast in Social Networks
http://www.mpi-inf.mpg.de/~tfried/paper/2012CACM.pdf

Measuring Behavioral Trust in Social Network
http://www.cs.rpi.edu/research/pdf/10-03.pdf

Time-Based Sampling of Social Network Activity Graphs
http://www.cs.purdue.edu/homes/neville/papers/ahmed-mlg2010.pdf


Massive Social Network Analysis: Mining Twitter for Social Good

http://www.cc.gatech.edu/~bader/papers/MassiveTwitter-ICPP2010.pdf


Understanding Latent Interactions in Online Social Networks

http://cs.ucsb.edu/~Ravenben/publications/pdf/renren-imc10.pdf

Facebook

As I introduced it a bit at yesterday's seminar, the crawled data set for Facebook is downloadable from the following URL.
http://suzumura-lab.blogspot.jp/2010/12/streamgraph-facebook-data.html

Status

雁瀬君 -> 坂本君が作っている X10 ベースの GIM-V 処理系をベースに スケーラブルなIncremental GIM-V 処理系を作る
上野君 -> general model for graph processing, SSSP for 8/8
渡部君 -> Giraph on TSUBAME, 性能分析
岡田君-> 感情分類器を作成中
小形君 -> ParGraph2012 の論文に着手
Charuwat 君 -> RDF data に対するグラフ解析の検討。BCを ParGraphに出す
橋川君->Twitter REST API を用いてクローラ開発

Important finding on Twitter REST API

Important finding on Twitter REST API
https://dev.twitter.com/docs/api

Machine Learning that Matters

http://d.hatena.ne.jp/repose/20120603/1338715703

Large Graph on multi-GPUs

http://developer.download.nvidia.com/GTC/PDF/GTC2012/PresentationPDF/S0241-GTC2012-Graph-Multi-GPUs.pdf

Clearing the clouds: a study of emerging scale-out workloads on modern hardware

http://dl.acm.org/citation.cfm?id=2150982

Graph related stuff

Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computationhttp://osl.iu.edu/publications/prints/2005/Gregor:OOPSLA:2005.pdf



Efficient Parallel Graph Exploration on Multi-Core CPU and GPU, PACT2011

http://ppl.stanford.edu/papers/pact11-hong.pdf



Accelerating CUDA Graph Algorithms at Maximum Warp, PPOP2007

http://ppl.stanford.edu/papers/ppopp070a-slides.pdf



Efficient Breadth-First Search on the Cell/B.E. Processor
http://www.dais.unive.it/~calpar/AA07-08/bfs.pdf



Optimizing Parallel Sparse Matrix-Vector Multiplication by Corner Partitioning, PARA08
http://www.sandia.gov/~egboman/papers/PARA08.pdf

Fast sparse matrix-vector multiplication by partitioning and reordering
http://igitur-archive.library.uu.nl/dissertations/2011-0913-201603/UUindex.html

More introduction stuff
http://www.cs.berkeley.edu/~skamil/cs267/notes/lect15NoteSpMV_kim.pdf

CACHE-OBLIVIOUS SPARSE MATRIX–VECTOR MULTIPLICATION BY
USING SPARSE MATRIX PARTITIONING METHODS

http://people.cs.kuleuven.be/~albert-jan.yzelman/PDFs/yzelman09-rev.pdf



Parallel Hypergraph Partitioning for Scientific Computing

http://www.cs.sandia.gov/~egboman/papers/IPDPS06.pdf



ON TWO-DIMENSIONAL SPARSE MATRIX PARTITIONING:
MODELS, METHODS, AND A RECIPE∗, 2010

http://graal.ens-lyon.fr/~bucar/papers/ucca2D.pdf


Application to protein-protein interaction network. 

A. Vazquez, A. Flammini, A. Maritan, and A. Vespignani.
Global protein function prediction in protein-protein interaction network
http://www.ncbi.nlm.nih.gov/pubmed/12740586


Application to computational phylogenetics 

B. Moret, D. Bader, and T. Warnow. High-performance algorithm engineering for computational phylogenetics. In
Proc. Int’l Conf. on Computational Science, volume 2073–
2074 of Lecture Notes in Computer Science, San Francisco,
CA, 2001. Springer-Verlag.


B. M. Moret, D. Bader, T. Warnow, S. Wyman, and M. Yan.
GRAPPA: a high-performance computational tool for phylogeny reconstruction from gene-order data. In Proc.
Botany, Albuquerque, NM, Aug. 2001.

Machine-Learning with Real-time and Streaming Applications

http://lyra.berkeley.edu/CDIConf/program.html

メモリ消費量を考慮したジョブスケジューリング

２年ほど前に書いた以下のエントリの問題は現実に必要な技術。
http://suzumura-lab.blogspot.jp/2010/07/blog-post_28.html

Apache Mahout

Machine Learning の Hadoop ベースのライブラリ Apache Mahout http://mahout.apache.org/
サポートされているアルゴリズム。

• Collaborative Filtering
• User and Item based recommenders
• K-Means, Fuzzy K-Means clustering
• Mean Shift clustering
• Dirichlet process clustering
• Latent Dirichlet Allocation
• Singular value decomposition
• Parallel Frequent Pattern mining
• Complementary Naive Bayes classifier
• Random forest decision tree based classifier
• High performance java collections (previously colt collections)
• A vibrant community

各自のタスク

各自のタスクの概要は以下の通りです。

Miyuru君: X10 Workshop @ Beijing 発表。SOCC2012投稿。ScaleGraphプロジェクトリード
上野君：HPDC発表準備/発表, ISC参加。ACS論文誌発表. 青柳君 X10 ベース ストリーム処理系ヘルプ、大規模グラフ処理基盤アーキテクチャ設計.
雁瀬君：WISE論文執筆。I-GIMV の追求. Apache Giraph 上への実装
渡部君：次の研究テーマ決め。Apache Giraph, HAMA, HBase などの実装。関連論文読み。I-GIMV論文読みなど
岡田君：イベント検知＋感情・評判分析を用いたストリーム処理基盤のアーキテクチャおよびコンポーネントの実装詳細設計
Charuwat君：BC最適化実装。RDF + DBPedia、グラフパターンマッチング調査
橋川君：ソーシャルネットワークのシミュレーション基盤構築。6月は Twitter のクローラー実装。
小形君：Spectral Clustering 。MAGMA による高速化。他のクラスタリングアルゴリズムの調査
バオ君：Apache Giraph の実装中身、サンプルアプリケーション、TSUBAME 上での性能評価など
金刺君：大規模エージェントシミュレーションのメッセージング機能の実装。データ同化 (Data Assimilation) が研究テーマ。

Pregel のオープンソース実装

バオ君の次の課題として、Pregel のオープンソース実装である Apache Giraph (http://incubator.apache.org/giraph/)を試してもらっている。Web ページを見ると、Fault Tolerancy などを鑑みて Hadoop/Zookeeper 上に実装されているようだ。性能面では ?? な実装である。

ちなみに、前にブログでも紹介したことがあるが、BSP(Bulk Synchronous Parallel)を実装している Apache Hama (http://incubator.apache.org/hama/)というプロジェクトもあるが、それとは関係ない。こちらはHDFS は使っているようだ。

また、Pregel のもう一つの実装である Bagel というのもある。以下の記事が参考になる。
http://d.hatena.ne.jp/smly/20110730/1312022963

Visualization for Large-scale Traffic Simulation

http://www.trsp.net/cow/video_trafficmixer.html

Visualizing the Kyoto road network by Prof.Hattori
http://www.youtube.com/watch?v=qYJLVZvvKR4&feature=relmfu
http://www.youtube.com/watch?v=I2vvIA9sKRo

Google Earth + KML による視覚化。いまいち。
http://www.youtube.com/watch?v=FEMOpMtenvE
http://www.youtube.com/watch?NR=1&feature=endscreen&v=bkR2ZcLHufI

Visualization with Google Earth
http://www.gtrek.co.uk/GTrek-Flight.kmz

IPDPS 2012 におけるグラフ処理に関する論文

Regular Track に8本もグラフに関する論文が採択されているところを見ると、大規模グラフに関する研究が近年ますます盛んになっている証拠である。http://www.ipdps.org/ipdps2012/2012_advance_program.html

Fast and Efficient Graph Traversal Algorithm for CPUs : Maximizing Single-Node Efficiency
Jatin Chhugani (Intel Corporation, USA); Nadathur Satish (Intel Corporation, USA); Changkyu Kim (Intel Corporation, USA); Jason Sewall (Intel Corporation, USA); Pradeep Dubey (Intel Corporation, USA)

SAHAD: Subgraph Analysis in Massive Networks Using Hadoop
Zhao Zhao (Virginia Tech, USA); Guanying Wang (Virginia Tech, USA); Ali R Butt (Virginia Tech., USA); Maleq Khan (Virginia Tech, USA); Vullikanti S Anil Kumar (Virginia Tech, USA); Madhav Marathe (Virginia Tech, USA)

Accelerating nearest neighbor search on manycore systems
Lawrence Cayton (Max Planck Institute for Intelligent Systems, Germany)

Optimizing large-scale graph analysis on multithreaded, multicore platforms
Guojing Cong (IBM T.J. Watson Research Center, USA)

Multi-core spanning tree algorithms using the disjoint-set data structure
Fredrik Manne (University of Bergen, Norway); Md. Mostofa Ali Patwary (Northwestern University, USA); Peder Refsnes (University of Bergen, Norway)
Graph Partitioning for Reconfigurable Topology
Deepak Ajwani (University College Cork, Ireland); Shoukat Ali (Dublin Research Lab, IBM, USA); John P. Morrison (University Cork, Ireland)
Multithreaded Clustering for Multi-level Hypergraph Partitioning
Umit V. Catalyurek (The Ohio State University, USA); Mehmet Deveci (The Ohio State University, USA); Kamer Kaya (The Ohio State University, USA); Bora Ucar (CNRS, France)              
Multithreaded Algorithms for Maximum Matching in Bipartite Graphs
Ariful Azad (Purdue University, USA); Mahantesh Halappanavar (Pacific Northwest National Laboratory, USA); Sivasankaran Rajamanickam (Sandia National Laboratories, USA); Erik G. Boman (Sandia National Laboratories, USA); Arif Khan (Purdue University, USA); Alex Pothen (Purdue University, USA)

情報拡散に関する研究

Information Transfer in Social Media, WWW 2012

Greg Ver Steeg, Aram Galstyan

The Role of Social Networks in Information Diffusion, WWW 2012

Eytan Bakshy, Itamar Rosenn, Cameron Marlow, Lada Adamic

Recommendations to Boost Content Spread in Social Networks, WWW 2012

Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, Rushi Bhatt

Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter, WWW 2011

http://www.cs.cornell.edu/home/kleinber/www11-hashtags.pdf

Limiting the Spread of Misinformation in Social Networks, WWW 2011 

Ceren Budak, Divyakant Agrawal and Amr El Abbadi

Information Credibility on Twitter, WWW, 2011 

Carlos Castillo, Marcelo Mendoza and Bárbara Poblete

Information Spreading in Contex, WWW 2011

Information diffusion in online social networks

http://www.eecs.harvard.edu/~parkes/nagurney/adamic.pdf

Survey Survey on Information Diffusion, 2008

http://www.cs.umd.edu/~getoor/cmsc828g/Slides/information-diffusion.pdf

Modeling Information Diffusion in Implicit Networks

http://cs.stanford.edu/people/jure/pubs/lim-icdm10.pdf

Information Diffusion Through Blogspace, WWW2004

http://people.csail.mit.edu/dln/papers/blogs/idib.pdf

We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model this collection at two levels. First, we present a macroscopic characterization of topic propagation through our corpus, formalizing the notion of long-running “chatter” topics consisting recursively of “spike” topics generated by outside world events, or more rarely, by resonances within the community. Second, we present a microscopic characterization of propagation from individual to individual, drawing on the theory of infectious diseases to model

the flow. We propose, validate, and employ an algorithm to induce the underlying propagation network from a sequence of posts, and report on the results.

CREST H23 年度 RA 成果報告会

CREST 平成23年度の RA の成果報告会を実施。パターンマッチング、スペクトラルクラスタリング、Random Walk with Restart、協調フィルタリング、ストリーム処理系の5つを5名の RA が実装。いずれも短期間ながら良い成果が出てきたと思います。今年も3名が引き続き、RA を続けていきます。小規模クラスタだけではなく、今年は TSUBAME を使った大規模実験およびそれに向けた最適化を実現したいと思います。