擴散範圍最大化之問題是從網路中找出能夠使訊息傳播的範圍最大之節點集合。由於網路之結構複雜且龐大，往往不易於資料分析及探勘，同時社群網路之興起，越來越多相關研究利用社群網路之結構來找出社群網路中，最有影響力之節點並期望能將擴散範圍最大化。本研究中共分為兩個部份：第一部份，藉著模組化函數之定義，選擇SetCover之路徑長度，並結合Label演算法將網路節點做分群。第二部份，在社群網路中利用SetCover之方法，找出社群中具備不同角色之節點。而在第二部份中，我們提出兩種不同的挑選方式選取節點。第一種是同時具備對於社群內及社群間最有影響力之節點；第二種是將對於社群內及社群間最有影響力之節點分別挑選。籍由提出社群化網路結構及影響力節點之挑選，能讓專家分析社群行為，有利於企業之口碑行銷手法，將產品推廣於不同社群中之使用者，以增加新客戶群；同時也有利於政府政策之推廣。The structure and scale of the Internet is tremendous. It’s not easy to do research in the domain of data analysis and data mining. With the rise of the social network, there are more and more research showing how to make use the structure of social network, and to find the most influence nodes to maximize the influence spread. This research is composed of two parts: In the first part, we will cluster the network by SetCover and Label algorithm, and apply the modularity function to determine the length of path. In the second part, we will propose two different methods to measure the influence rank of nodes in social network. For the first method, we consider about that the influence of node for their community and for all communities simultaneously. Different from first method, the second method select the most influence nodes for their communities. Next, we select the most influence node for the other communities as well. By proposing the selection of the influence nodes in the structure of social network, the behavior of social network could be analyzed by experts. It also can support web marketing for enterprises to spend less cost to reach maximum benefits.
