資訊搜尋近年已普遍的被應用於社群網路中。而以群為基準建構的社群網路裡，挑選合適的群首有助於使用者散播尋問訊息並且提升搜尋效率。因此，我們提出一個混合式資訊搜尋機制並且搭配動態權重之分散式標記分群輔助結構加速資訊搜尋速度。模擬結果顯示，相較於其他既有的機制，混合式資訊搜尋機制搭配動態權重之分散式標記分群輔助結構在資訊搜尋成功率、搜尋時間、重覆訊息比率上能取得較好的效能。

Information searches are the most common application within social network. Choosing the appropriate users as the clusterheads in a clustering-based social network facilitates the effective spread of query messages, resulting in effective search performance. To accomplish this, a hybrid search(HS) scheme is proposed, using a dynamic weighted distributed label clustering (DW-DLC) structure to facilitate searches. The DW-DLC structure accelerates the process of locating target information within social network. The simulation results show that the HS+DW-DLC scheme obtains a favorable balance among the search success rate, searching delay, and the amount of repeated messages.

[1] J.-S. Leu, C.-W. Tsai and W.-H. Lin, "Resource Searching in an Unstructured P2P Network Based on Cloning Random Walker Assisted by Dominating Set,"Computer Networks, Vo1. 55, No. 3, pp. 722-733, Feb. 2011.
[2] http://zh.wikipedia.org/wiki/
[3] http://skeletons.blogspot.com/2008/12/social-network.html
[4] http://en.wikipedia.org/wiki/Power_law
[5] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, "Search and replication in unstructured peer-to-peer networks," presented at the Proceedings of the 16th international conference on Supercomputing, New York, New York, USA, 2002.
[6] X. Zhu, J. Yu, W. Lee, D. Kim, S. Shan, and D.-Z. Du, "New dominating sets in social networks," J. of Global Optimization, vol. 48, pp. 633-642, 2010.
[7] F. Zou, Z. Zhang, and W. Wu, "Latency-Bounded Minimum Influential Node Selection in Social Networks," in Wireless Algorithms, Systems, and Applications. vol. 5682, B. Liu, A. Bestavros, D.-Z. Du, and J. Wang, Eds., ed: Springer Berlin Heidelberg, 2009, pp. 519-526.
[8] L. Jia, R. Rajaraman, T. Suel, "An efficient distributed algorithm for constructing small dominating sets, "Distributed Computing, Vol. 15, No. 4, pp. 193-205, Dec. 2002.
[9] L. Jia, R. Rajaraman, and T. Suel, "An efficient distributed algorithm for constructing small dominating sets," Distrib. Comput., vol. 15, pp. 193-205, 2002.
[10] B. Liang and Z. J. Haas, "Virtual backbone generation and maintenance in ad hoc network mobility management," in INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2000, pp. 1293-1302 vol.3.
[11] F. Kuhn and R. Wattenhofer., “Constant-time distributed dominating set approximation”, pp. 25-32, PODC 2003.
[12] G. Bo, Y. Yuhang, and M. Huiye, "An efficient approximation scheme for minimum connected dominating set in wireless ad hoc networks," in wireless ad hoc networks," in Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th, 2004, pp. 2744-2748 Vol. 4.
[13] W. Jie, "Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links," Parallel and Distributed Systems, IEEE Transactions on, vol. 13, pp. 866-881, 2002.
[14] J. Wu and H. Li, "On calculating connected dominating set for efficient routing in ad hoc wireless networks," presented at the Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, Seattle, Washington, USA, 1999.
[15] F. Dai and J. Wu, "An extended localized algorithm for connected dominating set formation in ad hoc wireless networks," Parallel and Distributed Systems, IEEE Transactions on, vol. 15, pp. 908-920, 2004.
[16] B. Han and W. Jia, "Clustering wireless ad hoc networks with weakly connected dominating set," J. Parallel Distrib. Comput., vol. 67, pp. 727-737, 2007.
[17] L. Jia, R. Rajaraman, and T. Suel, "An efficient distributed algorithm for constructing small dominating sets," Distrib. Comput., vol. 15, pp. 193-205, 2002.
[18] W. Aiello, F. Chung, and L. Lu, "A random graph model for massive graphs," presented at the Proceedings of the thirty-second annual ACM symposium on Theory of computing, Portland, Oregon, USA, 2000.