跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.81) 您好!臺灣時間:2025/02/13 08:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉貞宜
研究生(外文):Liu, Chen Yi
論文名稱:多重關係社群網路之高度連通群體
論文名稱(外文):Highly-Connected Communities in Multi-Relations Social Networks
指導教授:吳邦一
指導教授(外文):Bang Ye Wu
口試委員:吳邦一張貿翔黃耀廷陳彥宏
口試委員(外文):Bang Ye WuMaw-Shang ChangYao-Ting HuangYen Hung Chen
口試日期:2011/06/28
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:37
外文關鍵詞:cohesion groupcommunitydisjointmulti-relations social networksocial network analysisalgorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:404
  • 評分評分:
  • 下載下載:92
  • 收藏至我的研究室書目清單書目收藏:1
In this thesis, A new optimization problem \highly-connected-communities"
for detecting communities by means of connectivity on multi-relations social
networks is proposed. For nodes within a highly-connected-community, the
number of uni-color disjoint paths to any other is suciently large. Find-
ing a maximum highly-connected-community and minimum highly-connected-
community belongs to a classic problem named community detection. The
di erence is that, in this thesis, we consider multiple relations in a social
network. We propose a branch-and-bound algorithm for nding the minimum
highly-connected-community, as well as an approximation and a heuristic al-
gorithms. The experimental results show that the di erent algorithms have
their own advantages.
1 Introduction
2 Survey of Related Works
2.1 k-clubs
2.2 Influence-clubs
2.3 Flow modes
2.4 Connectivities
2.5 Random graphs
3 Preliminaries
3.1 Minimum highly-connected community problem
3.2 Maximum HCC problem
3.3 Computing the connectivities
4 Algorithms
4.1 Algorithms for Min HCC problem
4.2 Algorithms for Max HCC problem
5 Experimental results and discussions
5.1 Experimental results for Min HCC problem
5.2 Experimental results for Max HCC problem
6 Conclusions

[1] R.D. Alba, A graph-theoretic de nition of a sociometric clique, Journal
of Mathematical Sociology, 3:113{126, 1973.
[2] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flow : Theory,
Algorithm, And Applications, Prentice Hall, 1991.
[3] J.M. Bourjolly, G. Laporte and G. Pesant, Heuristics for nding k-clubs in
an undirected graph, Computers Operations Research, 27:559{569, 2000.
[4] J.M. Bourjolly, G. Laporte and G. Pesant, An exact algorithm for the
maximum k-club problem in an undirected graph, European Journal of
Operational Research, 138:21{28, 2002.
[5] G. Baier, Flows with Path Restrictions, PhD thesis, TU Berlin, 2003.
[6] U. Brandes and D. Fleischer, Centrality measures based on current
ow,
in Proceedings of the 22nd International Symposium on Theoretical As-
pects of Computer Science (STACS 05), Lecture Notes in Computer Sci-
ence, 3404:533{544, 2005.
[7] S.P. Borgatti, Centrality and network
ow, Social Networks, 27:55{71,
2005.
[8] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to
Algorithms, MIT Press and McGraw-Hill, 2001.
[9] E.A.Dinic, Algorithm for solution of a problem of maximum
ow in networks
with power estimation, Soviet Math. Dokl. II, pp.1277{1280, 1970.
[10] P. Erdos and A. Renyi, On random graphs, Publicationes Mathematicae,
6:290{297, 1959.
[11] L.C. Freeman, Centrality in networks: I. Conceptual clari cation, Social
Networks, pp.215{239, 1979.
[12] L.C. Freeman, S.P. Borgatti and D.R. White, Centrality in valued
graphs: A measure of betweenness based on network
ow, Social Net-
works, 13(2):141{154, 1991.
[13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide
to The Theory of NP-Completeness, W. H. Freeman & Co. New York,
NY, USA, 1979.
[14] M. Gendreau, P. Soriano and L. Salvail, Solving the maximum clique
problem using a tabu search approach, Annals of Operations Research
41:385{403, 1993.
[15] V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd and M. Yannakakis,
Near-Optimal Hardness Results and Approximation Algorithm
for Edge-Disjoint Paths and Related Problems, STOC`99, pp.19{28, 1999.
[16] G. Gutin and E.J. Kim, Properly coloured cycles and paths: results and
open problems, Golumbic Festschrift, LNCS 5420, pp.200{208, 2009.
[17] C.H. Hubbell, An input-output approach to clique detection, Sociome-
try, 28:277{299, 1965.
[18] R.A. Hanneman and M. Riddle, Introduction to Social Network Methods,
http://www.faculty.ucr.edu/hanneman/nettext/, 2005.
[19] R. Hassin, J. Monnot and D. Segev, Approximation algorithms and
hardness results for labeled connectivity problems, J. Comb. Optim.
14(4), pp.437{453, 2007.
[20] D.S. Johnson and M.A. Trick, editors, Second DIMACS Implementation
Challenge : Cliques, coloring, and Satisability, DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, American Mathematical
Society, 1996.
[21] L. Katz, A new status index derived from sociometric analysis, Psy-
chometrika, 18:39{43, 1953.
[22] R.J. Mokken, Cliques, clubs, and clans, Quality and Quantity, 13:161{
173, 1979.
[23] S. Micali and V.V.Vazirani, An O(
p
jV jjEj) algorithm for nding maximum
matching in general graphs, FOCS, pp.17{27, 1980.
[24] J.A. McHugh, Algorithmic Graph Theory, Prentice Hall, 1990.
[25] M.E.J. Newman, The structure and function of complex networks, SIAM
Review, 45:167{256, 2003.
[26] M.E.J. Newman, Mathematics of networks, The New Palgrave Encyclo-
pedia of Economics, Palgrave Macmillan, 2006.
[27] D.J. de S. Price, Networks of scienti c papers, Science, 149:510{515,
1965.
[28] N. Robertson and P.D. Seymour, Graph minors. XIII. The disjoint paths
problem, J. Comb. Theory, Series B 63, pp.65{110, 1995.
[29] R. Solomono and A. Rapoport, Connectivity of random nets, Bulletin
of Mathematical Biophysics, 13:107{117, 1951.
[30] P.D. Seymour, Disjoint paths in graphs, Discret. Math. 29, pp.293{309,
1980.
[31] Y. Shiloach, A polynomial solution to the undirected two paths problem,
J. ACM 27, pp.445{456, 1980.
[32] M. Stoer and F. Wangner, A Simple Min-Cut Algorithm, ACM, pp.585{
591, 1997.
[33] C.A. Tovey, A simpli ed NP-complete satis ability problem, Discret.
Appl. Math. 8(1), pp.85{89, 1984.
[34] C.-J. Tseng, and B.Y. Wu, Algorithms for detecting ow-based communities,
ITAOI, Taiwan, 2010.
[35] S. Wasserman and K. Faust, Social Network Analysis, Cambridge University
Press, Cambridge, 1994.
[36] B.Y.Wu, The maximum disjoint paths problem on multi-relations social
networks, available by arXiv:1104.4370, 2011.
[37] S. Yuan, S. Varma and J.P. Jue, Minimum-color path problems for reliability
in mesh networks, IEEE INFOCOM 2005 volume 4, pp.2658{2669,
2005.
[38] C.-P. Yang, H.-C. Chen, S.-D. Hsiea and B.Y. Wu, Heuristic Algorithms
for nding 2-clubs in an undirected graph, NCS, Taiwan, 2009.
[39] C.-P. Yang, C.-Y. Liu, and B.Y.Wu, In
uence Clubs in Social Networks,
ICCCI, LNAI 6422, Springer, 2010.
[40] UCINet, Release 6.0, Mathematical Social Science Group, Social School
of Science, University of California at Irvine.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top