[StreamGraph] Facebook Graph API

Facebook Graph API を用いれば実データは取れるそうだ。

------

The announcement was glossed over during Facebook’s many launches at f8 yesterday, but the company has introduced ways for developers to conduct a variety of searches for content in its Graph API. This could benefit any number of search companies and other developers who are looking for lots of public data to aggregate and organize.

The Open Graph allows applications, Pages, web sites and other software services to add Facebook features, like the “Like” button, to their own sites. Taking actions on other sites results in those actions being shared with your friends on Facebook, and may allow friends on those sites to see what you’re doing, too.

Many users have their privacy settings configured to allow status updates, likes and other activity to be public. Its terminology for this data is “public objects.” The generic search format is: https://graph.facebook.com/search?q=QUERY&type=OBJECT_TYPE.

Here are the specific types of searches that can be done:

All public posts: https://graph.facebook.com/search?q=watermelon&type=post

People: https://graph.facebook.com/search?q=mark&type=user

Pages: https://graph.facebook.com/search?q=platform&type=page

Events: https://graph.facebook.com/search?q=conference&type=event

Groups: https://graph.facebook.com/search?q=programming&type=group

News feeds of individuals can be searched, too, but you’ll need authorization. Here’s an example:

News Feed: https://graph.facebook.com/me/home?q=facebook

This search is restricted to public data about users and their immediate friends (not, say, their friends of friends), in keeping with Facebook’s existing data-sharing policies.

[StreamGraph] グラフアルゴリズムの GPU 化

Fast Mining Algorithms of Graph data on GPUs, LDMTA 2010

Scaling up the sparse matrix-vector multiplication kernel on modern Graphics Processing Units (GPU) has been at the heart of numerous studies in both academia and industry. In this article we present a novel approach to data representation for computing this kernel, particularly targeting sparse matrices representing power-law graphs. Using real data, we show how our representation scheme, coupled witha novel tiling algorithm, can yield signi ficant bene ts over the current state of the art GPU and CPU e orts on a number of core data mining algorithms such as PageRank, HITS and Random Walk with Restart.

http://arnetminer.org/confs/LDMTA2010/KDD-LDMTA-YangXintian.pdf

Accelerating Large Graph Algorithms on the GPU Using CUDA, 2007

http://www.springerlink.com/content/y4816x2q7475v93n/

Large graphs involving millions of vertices are common in many practical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. Graphics Processing Units (GPUs) of today have high computation power and low price. They have a restrictive programming model and are tricky to use. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA programming model. We present a few fundamental algorithms – including breadth first search, single source shortest path, and all-pairs shortest path – using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1.5 seconds using the Nvidia 8800GTX GPU costing $600. In some cases optimal sequential algorithm is not the fastest on the GPU architecture. GPUs have great potential as high-performance co-processors.

A Fast GPU Algorithm for Graph Connectivity, IPDPS 2010

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470817

raphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

[StreamGraph] Mixi Graph API

Mixi Graph API に関しては、パートナー契約が必要だそうで、登記簿などの提出が必要だそうです。なので、Mixi に大学などの研究組織に関しては、より手続きの簡素化ができるかどうか問い合わせをしておきました。

Mixi Graph API http://developer.mixi.co.jp/connect/mixi_graph_api

インターネットコンテンツの扱いに関して

著作権法改正案が国会提出、「ダウンロード違法化」など盛り込む

http://internet.watch.impress.co.jp/cda/news/2009/03/11/22747.html

文部科学省 著作権法の一部を改正する法律案

http://www.mext.go.jp/b_menu/houan/an/171/1251917.htm

文化庁のオフィシャルページ

http://www.bunka.go.jp/chosakuken/21_houkaisei.html

[StreamGraph] Netflix Challenge

ビデオレンタル会社 Netflix が依然実施した コンテスト (Netflix Prize: リコメンデーションの精度を10％以上向上させたら賞金) により、この分野における研究は大きく前進した。 当然、NetFlix は次のコンテストを企画していたそうだったが、個人を一意に特定できないことを証明することは難しく、プライバシーの問題でキャンセルしたそうだ。

http://www.techdirt.com/articles/20100312/1148468542.shtml

[StreamGraph] Graph 500

http://www.graph500.org/ のサイトが更新され、ランキングが出ています。

各種ネット企業の Web サービス API

価格.com の API http://apiblog.kakaku.com/KakakuItemInfoV1.0.html

Yahoo API http://developer.yahoo.co.jp/

楽天 Web サービス: http://webservice.rakuten.co.jp/

[StreamGraph] Social Graph API

最近, SNS の各社が Graph API を公開しだしているので、リストアップ。

Google Graph API http://code.google.com/intl/ja/apis/socialgraph/

- XFN（XHTML Friends Network）もしくはFOAF（Friend Of A Friend）を使用

- 使い方は、ここ などいろいろ記事があります。

Facebook Graph API http://developers.facebook.com/docs/api

Mixi Graph API

http://developer.mixi.co.jp/connect/mixi_graph_api/about_mixi_graph_api

SYSSTAT: Performance Analyzer

http://sebastien.godard.pagesperso-orange.fr/

VLDB 2010

http://www.vldb2010.org/proceedings/files/a_research.xml

p.472: The Performance of MapReduce: An In-depth Study
Dawei Jiang (National University of Singapore, Republic of Singapore), Beng Chin Ooi (National University of Singapore, Republic of Singapore), Lei Shi (National University of Singapore, Republic of Singapore), Sai Wu (National University of Singapore, Republic of Singapore)

p.129: Energy Management for MapReduce Clusters
Willis Lang (University of Wisconsin-Madison, United States of America), Jignesh Patel (University of Wisconsin-Madison, United States of America)

p.81: MapMerge: Correlating Independent Schema Mappings
Bogdan Alexe (University of California Santa Cruz, United States of America), Mauricio Hernández (IBM Research, United States of America), Lucian Popa (IBM Almaden Research Center, United States of America), Wang-Chiew Tan (University of California Santa Cruz, United States of Americ

p.449: iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques
Wook-Shin Han (Kyungpook National University, Republic of Korea), Jinsoo Lee (Kyungpook National University, Republic of Korea), Minh-Duc Pham (Kyungpook National University, Republic of Korea), Jeffrey Yu (The Chinese University of Hong Kong, People’s Republic of China)

p.340: On Graph Query Optimization in Large Networks
Peixiang Zhao (University of Illinois at Urbana-Champaign, United States of America), Jiawei Han (University of Illinois at Urbana-Champaign, United States of America)

p.330: Dremel: Interactive Analysis of Web-Scale Datasets
Sergey Melnik (Google, United States of America), Andrey Gubarev (Google, United States of America), Jing Jing Long (Google, United States of America), Geoffrey Romer (Google, United States of America), Shiva Shivakumar (Google, United States of America), Matt Tolton (Google, United States of America), Theo Vassilakis (Google, United States of America)

p.285: HaLoop: Efficient Iterative Data Processing on Large Clusters
Yingyi Bu (University of Washington, United States of America), Bill Howe (University of Washington, United States of America), Magdalena Balazinska (University of Washington, United States of America), Michael Ernst (University of Washington, United States of America)

p.264: Graph Pattern Matching: From Intractable to Polynomial Time
Wenfei Fan (University of Edinburgh, United Kingdom), Jianzhong Li (Harbin Institute of Technology, People’s Republic of China), Shuai Ma (University of Edinburgh, United Kingdom), Nan Tang (University of Edinburgh, United Kingdom), Yinghui Wu (University of Edinburgh, United Kingdom), Yunpeng Wu (National University of Defense Technology, People’s Republic of China)

p.276: GRAIL: Scalable Reachability Index for Large Graphs
Hilmi Yildirim (Rensselaer Polytechnic Institute, United States of America), Vineet Chaoji (Yahoo! Research Labs, United States of America), Mohammed Zaki (Rensselaer Polytechnic Institute, United States of America

p.220: High-Performance Dynamic Pattern Matching over Disordered Streams
Badrish Chandramouli (Microsoft Research, United States of America), Jonathan Goldstein (Microsoft Research, United States of America), David Maier (Portland State University, United States of America)

p.232: SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems
Irina Botan (Eidgenössische Technische Hochschule Zürich, Switzerland), Roozbeh Derakhshan (Eidgenössische Technische Hochschule Zürich, Switzerland), Nihal Dindar (Eidgenössische Technische Hochschule Zürich, Switzerland), Laura Haas (IBM Almaden Research Center, United States of America), Renée Miller (University of Toronto, Canada), Nesime Tatbul (Eidgenössische Technische Hochschule Zürich, Switzerland)

p.244: Recognizing Patterns in Streams with Imprecise Timestamps
Haopeng Zhang (University of Massachusetts Amherst, United States of America), Yanlei Diao (University of Massachusetts Amherst, United States of America), Neil Immerman (University of Massachusetts Amherst, United States of America)

Amazon Web Service の記事

玉川さんによる Amazon Web Service の記事

http://aws.typepad.com/aws_japan/

Streaming k-means approximation

Paper: http://books.nips.cc/papers/files/nips22/NIPS2009_1085.pdf

Video Lecture : http://videolectures.net/icml09_monteleoni_opakmo/

プロジェクト体制のまとめ

今の研究室のプロジェクト体制を再度まとめましょう.

1. StreamGPU チーム (松浦君、上野君)

2. StraemGraphチーム (西井君、雁瀬君）

3. StreamCloud ＆StreamDS チーム(石井君、松浦君）

4. StreamScale チーム (Miyuru 君、上野君)

GPU における ゼロコピー通信

　昨日の議論で思い出したのだが、カーネル空間のソケットバッファからユーザー空間を経ずに直接 GPU のメモリにコピーするような機構が、データストリーム処理に対する GPU の適用には有効であるので、それを追求すれば良い。1年ぐらい前の議論になると思うが、再考する価値はあるでしょう。

[StreamGraph] ターゲットアプリケーション

どれがストリーム向きなのかを明確にするために、ターゲットアプリケーションをリストアップしていき、分類分けをしていきましょう。Graph チームの皆さんも補足してください。

• グラフの中心性 (HITS, PageRank,マルコフ中心性)
• クラスタリング（Betweennessアルゴリズム, KMeans, ...) 、セミクラスタリング
• Triangle の抽出
• 2部グラフの最大マッチング
• 最短経路問題
• グラフ直径
• ...

[StreamGraph] Jung

Jung(Java Universal Network/Graph Framework)

http://jung.sourceforge.net/

ネットワーク(グラフ) 構造の分析や視覚化を行うためのJavaのOSSライブラリ.

グラフ理論、データマイニング、ソーシャルネットワーク分析のアルゴリズムを数多く実装

BSDライセンス

国内学会

[査読あり]

Webとデータベースに関するフォーラム (WebDB Forum) 毎年8月締め切り、11月開催

[査読なし]

電子情報通信学会 Web インテリジェンスとインタラクション研究会

http://www.ieice.org/~wi2/index.html

次回は2011年3月

[StreamGraph] Related Papers

Internet: Diameter of the World-Wide Web, Arbert Barabashi, 1999

http://www.nature.com/nature/journal/v401/n6749/abs/401130a0.html

Graphs over Time: Densification Laws, Shrinking Diameters and Possible, Jon Kleinberg, KDD 2005

Scale-free characteristics of random networks: The topology of the world-wide web, Albert Barabashi, 2000

[StreamGraph] Random Walk with Restart

H. Tong, C. Faloutsos, and J.-Y. Pan. Fast Random Walk with Restart and Its Applications. In Proceedings of International Conference of Data Mining, 2006

http://www.cs.cmu.edu/~christos/PUBLICATIONS/icdm06-rwr.pdf

A Unified Framework for Link RecommendationUsing Random Walks

http://www.cs.uiuc.edu/homes/hanj/pdf/asonam10_zyin.pdf

[StreamGraph] Triangle Law

Evolution of the social network of scientific collaborations, Barabashi, 2001

The co-authorship network of scientists represents a prototype of complex evolving networks. In
addition, it offers one of the most extensive database to date on social networks. By mapping the
electronic database containing all relevant journals in mathematics and neuro-science for an eightyear period (1991-98), we infer the dynamic and the structural mechanisms that govern the evolution and topology of this complex system. Three complementary approaches allow us to obtain a detailed characterization. First, empirical measurements allow us to uncover the topological measures that characterize the network at a given moment, as well as the time evolution of these quantities.
The results indicate that the network is scale-free, and that the network evolution is governed by
preferential attachment, affecting both internal and external links. However, in contrast with most model predictions the average degree increases in time, and the node separation decreases. Second, we propose a simple model that captures the network’s time evolution. In some limits the model can be solved analytically, predicting a two-regime scaling in agreement with the measurements. Third, numerical simulations are used to uncover the behavior of quantities that could not be predicted analytically. The combined numerical and analytical results underline the important role internal links play in determining the observed scaling behavior and network topology. The results and methodologies developed in the context of the co-authorship network could be useful for a systematic study of other complex evolving networks as well, such as the world wide web, Internet,or other social networks.

Structure of a large social network. Barabashi, et.al, 2003

We study a social network consisting of over 104 individuals, with a degree distribution exhibiting
two power scaling regimes separated by a critical degree kcrit, and a power law relation between
degree and local clustering. We introduce a growing random model based on a local interaction
mechanism that reproduces all of the observed scaling features and their exponents. Our results
lend strong support to the idea that several very different networks are simultenously present in the human social network, and these need to be taken into account for successful modeling

[StreamGraph] Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

http://www.cs.cmu.edu/~ctsourak/tsourICDM08.pdf

Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

How can we quickly nd the number of triangles in a large graph, without actually counting them? Triangles are important for real world social networks, lying at the heart of the clustering coe cient and of the transitivity ratio. However, straight-forward and even approximate counting algorithms can be slow, trying to execute or approximate the equivalent of a 3-way
database join. In this paper, we provide two algorithms, the Eigen-Triangle for counting the total number of triangles in a graph, and the EigenTriangleLocal algorithm that gives the count of triangles that contain a desired node. Additional contributions include the following: (a) We show that both algorithms achieve excellent accuracy, with up to 1000x faster execution time, on several, real graphs and (b) we discover two new power laws ( Degree-Triangle and TriangleParticipa-
tion laws) with surprising properties.

EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

PDF: http://www.cs.cmu.edu/~badityap/papers/eigenspokes-pakdd10.pdf

通話記録からのソーシャルグラフのパターン検知

EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

We report a surprising, persistent pattern in large sparse social graphs, which we term EigenSpokes. We focus on large Mobile Call graphs, spanning about 186K nodes and millions of calls, and find that
the singular vectors of these graphs exhibit a striking EigenSpokes pattern wherein, when plotted against each other, they have clear, separate lines that often neatly align along specific axes (hence the term “spokes”). Furthermore, analysis of several other real-world datasets e.g., Patent Citations, Internet, etc. reveals similar phenomena indicating this to be a more fundamental attribute of large sparse graphs that is related to their community structure. This is the first contribution of this paper. Additional ones include (a) study of the conditions that lead to such EigenSpokes, and (b) a fast algorithm for spotting and extracting tightly-knit communities, called
SpokEn, that exploits our findings about the EigenSpokes pattern

MapReduce 上のグラフアルゴリズム

Design Patterns for Efficient Graph Algorithms in MapReduce

http://www.umiacs.umd.edu/~jimmylin/publications/Lin_Schatz_MLG2010.pdf

Jimmy Lin, Michael Schatz, University of Maryland
Graphs are analyzed in many important contexts, including ranking search results based on the hyperlink structure of the world wide web, module detection of protein-protein interaction networks, and privacy analysis of social networks. MapReduce provides an enabling technology for large-scale graph processing. However, there appears to be a paucity of knowledge on designing scalable graph algorithms. Existing best practices for MapReduce graph algorithms have significant shortcomings that limit performance, especially with respect to partitioning, serializing, and distributing the graph. We present three design patterns that address these issues and can be used to accelerate a large class of graph algorithms based on message passing, exemplified by PageRank. Experiments show that the application of our design patterns reduces the running time of PageRank on a web graph with 1.4 billion edges by 69%.


Graph Processing with MapReduce
http://horicky.blogspot.com/2010/07/graph-processing-in-map-reduce.html

Twister: Iterative MapReduce

インディアナ大学の Jeffery Fox のグループが作っている Iterative な MapReduce 処理系
Twister http://www.iterativemapreduce.org/

[StreamGraph] Extended Library for Graph Processing

Standard Template Library for XXL Data Sets

http://www.springerlink.com/content/6drvfrkj7uu4hq0a/
We present a software library , that enables practice-oriented experimentation with huge data sets. is an implementation of the C++ standard template library STL for external memory computations. It supports parallel disks, overlapping between I/O and computation, and pipelining technique that can save more than half of the I/Os. has already been used for computing minimum spanning trees, connected components, breadth-first search decompositions, constructing suffix arrays, and computing social network analysis metrics.


Building a Parallel Pipelined External Memory Algorithm Library


Large and fast hard disks for little money have enabled the processing of huge amounts of data on a single machine. For this purpose, the well-established STXXL library provides a framework for external memory algorithms with an easy-to-use interface. However, the clock speed of processors
cannot keep up with the increasing bandwidth of parallel disks, making many algorithms actually compute-bound. To overcome this steadily worsening limitation, we exploit today’s multi-core processors with two new approaches. First, we parallelize the internal computation
of the encapsulated external memory algorithms by utilizing the MCSTL library. Second, we augment the unique pipelining feature of the STXXL, to enable automatic task parallelization.
We show using synthetic and practical use cases that the combination of both techniques increases performance
greatly.

PDF
http://algo2.iti.kit.edu/singler/publications/parallelstxxl-ipdps2009.pdf

Hadoop Summit 2010

http://developer.yahoo.com/events/hadoopsummit2010/agenda.html

[StreamGraph] Max-Cover in Map-Reduce

Max-Cover in Map-Reduce, WWW 2010

http://research.google.com/pubs/pub36582.html

The NP-hard Max-k-cover problem requires selecting k sets from a collection so as to maximize the size of the union. This classic problem occurs commonly in many settings in web search and advertising. For moderately-sized instances, a greedy algorithm gives an approximation of (1-1/e). However, the greedy algorithm requires updating scores of arbitrary elements after each step, and hence becomes intractable for large datasets. We give the first max cover algorithm designed for today's large-scale commodity clusters. Our algorithm has provably almost the same approximation as greedy, but runs much faster. Furthermore, it can be easily expressed in the MapReduce programming paradigm, and requires only polylogarithmically many passes over the data. Our experiments on five large problem instances show that our algorithm is practical and can achieve good speedups compared to the sequential greedy algorithm.

Apache HAMA

http://incubator.apache.org/hama/

Apache Hama is a distributed computing framework based on BSP (Bulk Synchronous Parallel) computing techniques for massive scientific computations (e.g., matrix, graph, network, ..., etc), currently being incubated as one of the incubator project by the Apache Software Foundation.

Paper
http://salsahpc.indiana.edu/CloudCom2010/papers.html

DisCo: Distributed Co-clustering with Map-Reduce: A Case Study towards Petabyte-Scale End-to-End Mining

DisCo: Distributed Co-clustering with Map-Reduce: A Case Study towards Petabyte-Scale End-to-End Mining, 2008, ICDM

PDF http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.163.1677&rep=rep1&type=pdf

Huge datasets are becoming prevalent; even as researchers, we now routinely have to work with datasets that are up to a few terabytes in size. Interesting real-world applications produce huge volumes of messy data. The mining process involves several steps, starting from pre-processing the raw data to estimating the final models. As data become more abundant, scalable and easy-to-use tools for distributed processing are also emerging. Among those, Map-Reduce has been widely embraced by both academia and industry.

[StreamGraph] PEGASUS (Peta Graph Mining System)

Project URL http://www.cs.cmu.edu/~pegasus/

Paper URL ->
http://www.cs.cmu.edu/~ukang/papers/PegasusICDM2009.pdf

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

In this paper, we describe PEGASUS, an open source Peta Graph Mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node and finding the connected components. As the size of graphs reaches several Giga-, Tera- or Peta-bytes, the necessity for such a library grows too. To the best of our knowledge, PEGASUS is the first such library, implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. Many graph mining operations (PageRank, spectral clustering,diameter estimation, connected components etc.) are essentially a repeated matrix-vector multiplication. In this paper we describe a very important primitive for PEGASUS, called GIM-V (Generalized Iterated Matrix-Vector multiplication). GIM-V is highly optimized, achieving (a) good scale-up on the number of available machines (b) linear running time on thenumber of edges, and (c) more than 5 times faster performance over the non-optimized version of GIM-V. Our experiments ran on M45, one of the top 50 supercomputers in the world. We report our findings on several real graphs, including one of the largest publicly available Web Graphs, thanks to Yahoo!, with 6,7 billion edges.