可信度傳遞演算法為處理機率圖形模型時常用的演算法。但隨著網際網路的快速發展，網路上的資訊也呈現爆發性的成長，這使得我們在使用可信度傳遞演算法做分析這些資料所成的圖時變得需要更多的時間來做計算。同時，在可信度傳遞演算法執行的每一回合裡，系統也需要大量的空間來儲存各節點間所要傳遞的訊息。
在這篇論文裡，我們使用由上而下(top-down protocol)的概念提出的一個由上而下的可信度傳遞演算法(Top-Down Belief Propagation)的傳遞方式，我們比較圖中各節點的連結個數的大小來決定訊息傳遞的方向。如此一來，原本在正常可信度傳遞演法每一回合裡，我們本來需要計算出兩倍乘上邊數的訊息量，而在我們所提出的方法裡，我們每一回合所要計算的訊息量最多可以減少至原本的一半。這使得我們的由上而下的可信度傳遞傳演算能夠達到更高的效率。在我們的實驗中，我們將提出的方法應用在社群網路等具有小世界現上，我們發現在這些資料集上，我們的方法能得到與原本可信度傳遞演算同樣或更高的正確率，而且也達到了我們預期的快速及節省空間的效果。最後，我們也討論了我們的方法在應用圖片的資料集時所會遇到的問題及實際使用的結果。

Belief propagation is an algorithm in probabilistic graphical models. With the fast development of Internet, the graph becomes larger and larger. When we use belief propagation to analyze these graphs, it not only costs more time to compute the messages but also needs more space to save the messages in each iteration.

In this thesis, we applied a top-down protocol to belief propagation algorithm and proposed the ``Top-Down Belief Propagation (TDBP)''. We consider the degree's distribution of a graph and find a feasible message passing ordering. In original belief propagation, it needs to compute 2|E| messages in each iteration, but in our proposed method, we can reduce at most a half of computations. It makes the belief propagation becomes faster. In our experiment, our proposed method can works very well in social network datasets which contains the small-world phenomenon. The results show that our method is more efficient under the premise of equal or higher accuracy than original belief propagation. At the same time, we also can save almost a half of spaces as we expected. In the end, we discuss the difficulties when implement our method on image and give some results.

[1] C. M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[2] J. Crank. The Mathematics of Diffusion. Clarendon Press, 1979.
[3] P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. Mathematical Association of America, Washington, DC, 1984.
[4] E. N. Gilbert. Random graphs. Annals of Mathematical Statistics, 30(4):1141–1144, 1959.
[5] M. Jordan and Y. Weiss. Probabilistic inference in graphical models. Handbook of neural networks and brain theory, 2002.
[6] D. Koutra, T.-Y. Ke, U. Kang, D. H. Chau, H.-K. K. Pao, and C. Faloutsos. Unifying guilt-by-association approaches: Theorems and fast algorithms. In ECML/PKDD (2), pages 245–260, 2011.
[7] L. Lovsz. Random walks on graphs: A survey, 1993. 37
[8] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27(1):415–444, 2001.
[9] S. Milgram. The Small World Problem. Psychology Today, 2:60–67,1967.
[10] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
[11] A. L. Traud, P. J. Mucha, and M. A. Porter. Social structure of facebook networks. arXiv:1102.2166, 2011.
[12] D. J. Watts and S. H. Strogatz. Collective dynamics of’small-world’networks. Nature, 393(6684):409–10, 1998.
[13] Y. Weiss and W. T. Freeman. Correctness of belief propogation in Gaussian graphical models of arbitrary topology. Technical Report UCB/CSD-99-1046, EECS Department, University of California, Berkeley, Jun 1999.