(3.236.231.14) 您好！臺灣時間：2021/04/11 23:46

### 詳目顯示:::

:

• 被引用: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 Introduction1.1 Social networks1.2 Balance theory1.3 Signed graphs2 Preliminaries and related works2.1 Related works2.1.1 Clustering with partial information2.1.2 Balancing a complete signed graph by changing minimum number of edge signs2.1.3 Modularity2.2 Preliminaries3 Algorithms3.1 Exact algorithms3.2 A heuristic algorithm4 Experimental results4.1 Lower bound for algorithm efficiencies4.2 Node selection method for branching4.3 Heuristic algorithm4.3.1 Performance of the heuristic algorithm4.3.2 Real data4.4 Discussion5 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 藉由實驗的方式研究圖論上邊修改問題 2 最大平衡子圖之演算法 3 基於強健連結以偵測社會網路上之真實朋友 4 藉由改變最少正負號以平衡完全圖 5 在有號完全圖上尋找大的平衡子集之演算法 6 多重關係社群網路之高度連通群體 7 在社群網路上尋找真實朋友連結的結構性方法

 無相關期刊

 1 最大有限分支度一集合問題之啟發式演算法與分支化約演算法研究 2 模擬社會網路生成的改進模型 3 藉由實驗的方式研究圖論上邊修改問題 4 對社會網路的抽樣方法 5 標籤不均衡資料與學習有效分類器之樣本挑選法 6 最小三命中集合問題之新啟發式演算法設計與分析 7 基於平衡理論的社會網路行銷推薦系統 8 擴充OpenMP以支援軟體實現執行緒層級推測技術之研究 9 行動裝置之資訊訂閱服務 10 含地理位置服務的電子商務搜尋引擎設計與實作 11 類比電路運算放大器 自動繞線 12 藉由靜態程式碼分析找出Android惡意程式潛在的惡意行為 13 Fine-grained Classification of Web Traffic 14 用於多媒體分析與檢索的隱私保護二元圖配對架構 15 最大有限分支度d集合問題之啟發式演算法設計與分析

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室