計算社群網路Tree-depth之啟發式演算法

Heuristic algorithms for tree-depth of social networks

呂家豪(CHIA-HAO LU)

指導教授 ： 吳邦一

國立中正大學/工學院/資訊工程學系/碩士(2016年)

並列摘要

The tree-depth of a graph G is the minimum height of rooted forest F such that G ⊆ closure(F), where closure(F) is the graph obtained from F by adding all possible edges between ancestors and descendants. We implemented a dynamic programming algorithm for finding the tree-depth and designed heuristic algorithms based on using betweenness, closeness, triangle, and degree centralities. We did several experiments to evaluate the performances of our heuristic algorithms on social networks of different models. We also proposed heuristic algorithms based on the tree-depth decomposition tree for the graph coloring problem and the maximum independent set problem. For the graph coloring problem, we studied some cases that our heuristic algorithm is much better than the degree-first method. For the maximum independent set problem, our heuristic algorithm performs very well in our experiments.

並列關鍵字

Maximum independent set ； Graph coloring ； Social network ； Tree-depth

參考文獻

[1] A. Bavelas. Communication patterns in task-oriented groups. The Journal of the Acoustical Society of America, 22(6):725-730, 1950.

[3] S. P. Borgatti. Centrality and network flow. Social Networks, 27(1):55-71, 2005.

[4] U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163-177, 2001.

[6] F. V. Fomin, A. C. Giannopoulou, and M. Pilipczuk. Computing tree-depth faster than 2^n. Algorithmica, 73(1):202-216, 2014.

[7] L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35-41, 1977.