(3.236.231.14) 您好!臺灣時間:2021/04/11 23:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳佳芬
研究生(外文):Jia-Fen Chen
論文名稱:藉由改變最少正負號和刪點以平衡完全圖
論文名稱(外文):Balancing a complete signed graph by editing edges and deleting nodes
指導教授:吳邦一
指導教授(外文):Bang Ye Wu
口試委員:吳邦一張貿翔李新林黃耀廷
口試委員(外文):Bang Ye WuMaw-Shang ChangSing Ling LeeYao-Ting Huang
口試日期:2013-06-28
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:49
中文關鍵詞:有號圖平衡圖分支定界法演算法社會網路分析
外文關鍵詞:signed graphbalanced graphbranch and boundalgorithmsocial network analysis
相關次數:
  • 被引用被引用:0
  • 點閱點閱:171
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:2
一個無向有號圖,它的邊可以被標記為正號或負號。
如果有號圖內的每個cycle的負號邊數量皆為偶數,那該圖即為平衡。在此論文中,我們要研究的問題是藉由改最少的正負號和刪點以平衡完全圖。我們設計一個branch-and-bound演算法和heuristic演算法。我們可以藉由實驗結果顯示出branch-and-bound演算法和heuristic演算法是有效的。heuristic演算法使用一個技巧:考慮α 個點去決定一個點。我們也有把該演算法應用在community detection問題上。我們用兩個已知的benchmark去驗證heuristic演算法。
A signed graph is a simple undirected graph in which each edge is either positive or negative.
A signed graph is balanced if every cycle has even numbers of negative edges. In this thesis we study the problem of balancing a complete signed graph by minimum editing cost, in which the editing operations includes inserting edges, deleting edges, and deleting nodes. We design a branch-and-bound algorithm, as well as a heuristic algorithm. By experimental results we show that the branch-and-bound algorithm is much efficient than a trivial one and the heuristic algorithm performs well. The heuristic algorithm uses the look-ahead technique: one-by-one deciding one node by checking α nodes. We also applied the algorithm to the community detection problem. We demonstrate the heuristic algorithm with applications to two benchmarks for which the community structures are already known.
1 Introduction
1.1 Social networks
1.2 Balance theory
1.3 Signed graphs

2 Preliminaries and related works
2.1 Related works
2.1.1 Clustering with partial information
2.1.2 Balancing a complete signed graph by changing minimum number of edge signs
2.1.3 Modularity
2.2 Preliminaries

3 Algorithms
3.1 Exact algorithms
3.2 A heuristic algorithm

4 Experimental results
4.1 Lower bound for algorithm efficiencies
4.2 Node selection method for branching
4.3 Heuristic algorithm
4.3.1 Performance of the heuristic algorithm
4.3.2 Real data
4.4 Discussion

5 Conclusion

[1] S. Böcker and P. Damaschke, Even faster parameterized cluster deletion and cluster editing, Information Processing Letters, 111(14):717-721, 2011.

[2] S. Böcker, S. Briesemeister, Q.B.A. Bui, A. Truss, Going weighted: Parameterized algorithm for cluster editing, Theor. Comput. Sci., 410(52):5467-5480, 2009.

[3] J. Chen, J. Meng, A 2k kernel for the cluster editing problem, in: M.T. Thai, S. Sahni (Eds.), Computing and Combinatorics Conf., COCOON 2010, in: LNCS, vol. 6196, 2010, pp. 459-468.

[4] P. Damaschke, Bounded-degree techniques accelerate some parameterized graph algorithms, in: J. Chen, F.V. Fomin (Eds.), Int. Workshop on Parameterized and Exact Comp., IWPEC 2009, in: LNCS, vol. 5917, 2009, pp. 98-109.

[5] P. Damaschke, Fixed-parameter enumerability of cluster editing and related problems, Theory Computing Syst., 46, 61-283, 2010.

[6] M. R. Fellows, J. Guo, C. Komusiewicz, R. Niedermeier, J. Uhlmann, Graph-based data clustering with overlaps, Discrete Optimization, 8(1), 2-17, 2011.

[7] J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, Graph-modeled data clustering: Fixedparameter algorithms for clique generation, Theory Computing Syst., 38, 373-392, 2005.

[8] J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica, 39, 321-347, 2004.

[9] J. Guo, A more effective linear kernelization for cluster editing, Theor. Comput. Sci. 410, 718-726, 2009.

[10] F. Harary, On the notion of balance of a signed graph, Michigan Mathematical Journal, pp.143-146, 1953.

[11] F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier, Fixed-parameter algorithms for cluster vertex deletion, Theory of Computing Systems, 47(1), 196-217, 2010.

[12] R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

[13] R. Shamir, R. Sharan, D. Tsur., Cluster graph modification problems, Proceedings of 28th Workshop on Graph Theory (WG), pp. 379-390, 2002.

[14] P.-S. Wei and B.Y. Wu, Balancing a complete signed graph by changing minimum number of edge signs, in Proceedings of the 29th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2012.

[15] F. Heider, Attitudes and cognitive organization, Journal of Psychology, pp. 107-112, 1946.

[16] Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Frances Rosamond, Clustering with partial information, Theoretical Computer Science, 411:1022-1211, 2010.

[17] M. E. J. Newman, Modularity and community structure in networks, PNSA USA, 103:8577-8585, 2006.

[18] S. Wasserman, K. Faust, Social Network Analysis, Cambridge University Press, Cambridge, 1994.

[19] W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33:452-473, 1977.

[20] D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten, S.M. Dawson, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology, 54:396-405, 2003.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔