In this paper, we introduce a simple and new idea of link partition algorithm, direct line graph partition(DLP), using line graph transformation and traditional partition method. Two well-known algorithms, CPM(Clique Percolation method) and link clustering(LC) method, are introduced and compared to DLP. Since a usual line graph has more edges and nodes than its original graph, we selected
faster partition algorithms, Fastgreedy and Walktrap, for line-graph partition.
To compare goodness of algorithms, we adopt Mov. DLP is faster than CPM and shows better goodness of overlapping clustering. Concept of pair-wise link similarity is also applied to improve goodness of DLP. However, WDLP takes more time than DLP and shows almost same Mov. Briey speaking, there`s no considerable improvement goodness.
In addition, we propose an algorithm, Finding-Local-Optimum (FLO), that nds a clustering with a local optimum when an objective function is given. We have conducted a set of experiments on networks. The result shows that methods based on WDLP and DLP with FLO produces a higher
accuracy compared to LC. It`s complexity is smaller than CPM. Since CPM`s de nition is too strict, it rarely returns overlapping clusters which covers all nodes in network. If one wants to do overlapping clustering with every node in a given network, DLP and WDLP can be good candidates for this.
이 논문에서는 중복이 허용되는 군집화의 방법으로 라인그래프를 군집화하는 DLP와 라인그래프에 가중치를 주는 WDLP를 소개하고 기존의 중복이 허용되는 군집화 방법들인 CPM과 연결 군집화방법들과의 비교를 하고 있다.
비교를 위해서 최근에 알려진 측도를 도입하였으며, 기존 군집화와 비교하여 유사하거나 우수한 결과를 보인다는 것을 확인하였다. DLP의 중간 과정에서 연결들 간의 가중치를 고려하는 WDLP의 경우 오히려 낮거나 비슷한 수준의 좋은 측도값을 보였다.
CPM의 경우 전체적으로 좋은 측도값을 보이나 전체 노드를 포함하는 군집을 보이지 않기 때문에 천체 노드를 포함하는 군집을 원할 경우 DLP나 WDLP가 좋은 대안이 될 수 있을것이다.
추가적으로 측도의 지역 최적값을 찾기 위한 추가적인 과정을 도입하여 더 낳은 값을 찾도록 하는 시도를 해보았으며 초기 결과에 비해 향상된 결과를 보인다는 것을 확인했다. 문제는 이 과정에서 발생하는 코스트가 지나치게 크다는 것이며, 이 것을 해결하기 위해 노드 중에서 betweennes가 큰 노드를 선별적으로 선택해 부분적으로만 지역 최적값을 찾도록 방법을 수정했으며 이 경우 10%내외의 작은 부분을 이용하지만 충분히 괜찮은 측도값의 향상을 발견할 수 있었다.
