대규모 네트워크에서 Modularity를 이용한 향상된 커뮤니티 추출 알고리즘

한치근 ( Chi-geun Han ),조무형 ( Moo-hyoung Jo ) 한국인터넷정보학회 2012 인터넷정보학회논문지 Vol.13 No.3

본 논문에서는 modularity를 기반으로 한 향상된 커뮤니티 추출 알고리즘을 제안한다. 기존의 알고리즘은 modularity 값을 증가시키는 커뮤니티를 구축할 때 노드가 갖고 있는 정보를 고려하지 않음으로써, 계산을 비효율적으로 반복하여 수행한다. 제안하는 알고리즘은 노드의 degree(weight)를 계산하고 그것을 내림차순으로 정렬하고, 정렬된 순서대로 modularity 값의 증가여부를 확인함으로써, 반복되는 계산과정을 줄여 기존의 알고리즘보다 빠르게 최종 결과를 도출해낸다. 실험계산을 통해 제안하는 알고리즘이 더 짧은 시간 내에, 기존알고리즘이 구한 modularity 값보다 같거나, 향상된 값을 찾는다는 것을 보인다. In this paper, an improved community detection algorithm based on the modularity is proposed. The existing algorithm does not consider the information that the nodes have in checking the possible modularity increase, hence the computation may be inefficient. The proposed algorithm computes the node degree (weight) and sorts them in non-increasing order. By checking the possible modularity value increase for the nodes in the nonincreasing order of node weights, the algorithm finds the final solution more quickly than the existing algorithm does. Through the computational experiments, it is shown that the proposed algorithm finds a modularity as good as the existing algorithm obtains.

대규모 계산 공학 문제를 위한 내부점 알고리즘의 응용

한치근(Chi-Geun Han) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.8

이 논문에서는 공학 분야에서 발견되는 옵스터클 문제와 일레스틱-플레스틱 토션 문제를 풀기 위한 다항 함수시간의 내부점 알고리즘의 응용을 설명한다. n이 변수의 갯수, L이 문제의 크기일 때 응용된 내부점 알고리즘의 복잡도는 O(n^(35)L)로 주어진다. IBM 3090-600S 상에서 49만개의 변수를 갖고 있는 문제까지 풀어 얻어진 결과로 제안된 알고리즘의 최종해가 충분한 정확도를 갖고 있음을 알 수 있다. 얻어진 해들을 컴퓨터 그래픽으로 표현한 그림들은 모든 변수들이 최종해를 향하여 동시에 움직이고 있음을 보여주고 있다. We apply a polynomial time interior-point algorithm for solving some large-scale engineering problems such as obstacle problems and elastic-plastic torsion problems. The time complexity of the algorithm is O(n^(35)L) when n is the number of variables and L is the size of the input data of the problem. Computational results obtained by solving problems up to half a million variables on IBM 3090-600S show that the final solutions have sufficient accuracy. Graphical representation of the solutions shows that the algorithm finds a sequence of solutions where all variables are moving to the optimum simultaneously.

에지 한 개 추가에 따른 그래프의 고유벡터 중심성 변화 분석

한치근(Chi-Geun Han),이상훈(Sang-Hoon Lee) 한국컴퓨터정보학회 2016 韓國컴퓨터情報學會論文誌 Vol.21 No.1

There are many methods to describe the importance of a node, centrality, in a graph. In this paper, we focus on the eigenvector centrality. In this paper, an analytical method to estimate the difference of centrality with an additional edge in a graph is proposed. In order to validate the analytical method to estimate the centrality, two problems, to decide an additional edge that maximizes the difference of all centralities of all nodes in the graph and to decide an additional edge that maximizes the centrality of a specific node, are solved using three kinds of random graphs and the results of the estimated edge and observed edge are compared. Though the estimated centrality difference is slightly different from the observed real centrality in some cases, it is shown that the proposed method is effective to estimate the centrality difference with a short running time.

교통망의 강건성 민감도를 이용한 특정 구간의 정체에 의한 파급효과 분석

한치근(Chi-Geun Han),이성근(Sung-Geun Lee) 한국컴퓨터정보학회 2023 韓國컴퓨터情報學會論文誌 Vol.28 No.4

본 연구는 특정 구간의 정체가 전체 고속도로에 미치는 영향을 분석하기 위한 고속도로 망의 강건성 민감도 지수(RSI: robustness sensitivity index)를 제안한다. 새로 제안된 RSI는 특정 구간의 길이가 연장되었을 때, 연장된 단위 길이 당 교통망의 총 운행거리 변화량으로 정의한다. RSI 값이 클 경우, 해당 구간의 교통 정체는 다른 구간에 비해 전체 망에 나쁜 영향을 미치게 된다. 기존의 망 강건성 지수(NRI: network robustness index)는 단순히 특정 구간이 있을 때와 없을 때의 교통망 변화를 관찰하지만, 본 연구가 제안한 RSI는 일종의 성능 지표로 특정 구간의 정체 정도에 따른 망 전체의 파급효과를 정량적으로 분석할 수 있게 해준다. 특정 구간의 정체 정도를 변화시키면서, 그 정체가 발생시키는 다른 구간들의 교통량 증가, 감소, 정체 구간의 크기 및 위치 등이 어떻게 변화하는지를 계산할 수 있다. 이 분석은 NRI로는 분석 불가능한 것으로 RSI의 우수성을 입증하는 것이다. 국내 고속도로 망의 데이터를 이용해 RSI의 다양한 성질을 분석한다. 그리고 RSI 개념을 이용하면 특정 구간의 정체 정도 변화가 발생시키는 다른 구간들에 대한 파급효과를 분석할 수 있음을 보인다. In this paper, we propose a robustness sensitivity index (RSI) of highway networks to analyze the effect of congestion in a specific section on the entire highway. The newly proposed RSI is defined as the change in the total mileage of the transportation network per extended unit length when the length of a particular section is extended. When the RSI value is large, traffic congestion in the section has a worse effect on the entire network than in other sections. The existing network robustness index (NRI) simply observes changes in transportation networks with and without specific sections, but the RSI proposed in this study is a kind of performance indicator that allows quantitative analysis of the ripple effect of the entire network according to the degree of congestion in a specific section. While changing the degree of congestion in a particular section, it is possible to calculate how the traffic volume increases, decreases, and the size and location of the congestion section change. This analysis proves the superiority of RSI as it cannot be analyzed with NRI. Various properties of RSI are analyzed using data from the domestic highway network. In addition, using the RSI concept, it is shown that the ripple effect on other sections in which a change in the degree of congestion of a specific section occurs can be analyzed.

실험계산을 통한 에지 한 개 추가에 따른 그래프의 중심성 및 순위 변화 분석

한치근 ( Chi-geun Han ),이상훈 ( Sang-hoon Lee ) 한국인터넷정보학회 2015 인터넷정보학회논문지 Vol.16 No.5

그래프에서 각 노드에 대해 그래프 내의 중요도를 나타내는 중심성(centrality)을 계산할 수 있고, 그 값에 따라 각 노드는 중요도 순위(ranking)를 갖는다. 중심성을 나타내는 방법으로는 여러 척도가 있는데, 본 연구에서는 연결도(degree) 중심성, 밀접도(closeness) 중심성, 특성벡터(eigenvector) 중심성, betweenness 중심성에 국한하여 연구를 수행하였다. 본 연구는 그래프에서 에지를 하나 추가할 경우, 그래프 내 노드 전체에 미치는 노드의 중심성 및 순위의 변화를 실험계산을 통해 확인한다. 그리고, 추가되는 에지가 노드 전체의 중심성 및 순위에 미치는 영향은 그래프의 형태에 따라 달라진다는 것을 PCA(Principal Component Analysis)를 통해 밝혔다. 이 사실은 그래프의 구조적 특성을 구분하는 방법으로도 사용될 수 있다. The centrality is calculated to describe the importance of a node in a graph and ranking is given according to the centrality for each node. There are many centrality measures and we use degree centrality, closeness centrality, eigenvector centrality, and betweenness centrality. In this paper, we analyze the effect of an additional edge of a graph on centrality and ranking through experimental computations. It is found that the effect of an additional edge on centrality and ranking of the nodes in the graph is different according to the graph structure using PCA. The results can be used for define the graph characteristics.

멀티캐스트 라우팅을 위한 Ant Colony System 설계에 대한 연구

이성근,한치근,Lee, Sung-Geun,Han, Chi-Geun 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.4

조합 최적화 문제를 풀기 위한 개미 알고리즘(Ant Algorithm)은 실제 개미 집단의 행동을 모방하여 만들어진 것이다. Ant Colony System(ACS)은 여러 유형의 개미 알고리즘 중 비교적 최근에 소개된 것이다. ACS의 설계를 위해 순회 외판원 문제(Traveling Salesman Problem, TSP)를 사용하여 실험을 수행하였다. ACS를 다양한 조합 최적화 문제에 적용할 때 순회 외판원 문제에 사용된 ACS의 파라미터와 전략을 사용하고 있다. 본 논문에서는 조합 최적화 문제들 중 하나인 멀티캐스팅 라우팅 문제를 해결하기 위해 ACS를 이용하였다. 멀티캐스트 라우팅은 데이터를 하나의 송신자에서 여러 수신자들로 보내기 때문에 모든 노드를 포함하는 순회 외판원 문제와는 속성이 다르고, 송신자에서 각 수신자에 하나의 최단경로를 설정하는 문제와도 다른 속성을 지니고 있다. 본 논문에서는 멀티캐스트 라우팅에 ACS를 적용하기 위해 알고리즘의 동작을 수정하고, 수정한 ACS의 성능을 향상시키기 위한 최적의 전략과 파라미터를 설계한다. Ant Algorithm is used to find the solution of Combinatorial Optimization Problems. Real ants are capable of finding the shortest path from a food source to their nest without using visual informations. This behavior of real ants has inspired ant algorithm. There are various versions of Ant Algorithm. Ant Colony System (ACS) is introduced lately. ACS is applied to the Traveling Salesman Problem (TSP) for verifying the availability of ACS and evaluating the performance of ACS. ACS find a good solution for TSP When ACS is applied to different Combinatorial Optimization Problems, ACS uses the same parameters and strategies that were used for TSP. In this paper, ACS is applied to the Multicast Routing Problem. This Problem is to find the paths from a source to all destination nodes. This definition differs from that of TSP and differs from finding paths which are the shortest paths from source node to each destination nodes. We introduce parameters and strategies of ACS for Multicasting Routing Problem.

관로가 있는 생존가능망 설계에 관한 효율적인 알고리즘 연구

강효관,한치근,Kang, Hyo-Kwan,Han, Chi-Geun 한국정보처리학회 2001 정보처리학회논문지 C : 정보통신,정보보안 Vol.8 No.5

Network is changed from voice-based network into multimedia-based network by development of communication technology and multimedia service. We need a large bandwidth for multimedia service. The optical fiber is a more suitable medium than existing copper-based cable for large bandwidth. But, it is so expensive than copper-based cable. So, Minimizing total cost becomes a more important concept. In order to construct a minimum cost network, we have to consider existing conduits in network. On the other hand, optical fiber network allows that larger amount of traffic can be transmitted than copper-based network does. However, a failure of a node or link can make a serious damage to the network service. Thus, we have to get multiple paths to support continuous service even if a loss of failure occurs in some point of the network. The network survivability problem is to design the network that can provide reliable service to customers anytime with minimum total cost. In an existing solution of the network survivability problem with conduits, a conduit is considered only one time. But, the conduit is reusable if the network satisfies the required survivability. Proposed algorithm can more effectively considered already existed conduit. Network survivability and edge cost is predetermined. The proposed algorithm finds the best solution by conduit sharing within the limits of network survivability. According to the simulation result, the proposed method can decrease 7% of total cost than an existing method by effective conduits adaption. 최근 각종 멀티미디어 서비스의 제공은 전송데이터의 급격한 증가를 가져왔으며, 이러한 서비스의 원활한 제공을 위해서는 초고속 통신망의 구축이 불가피하게 되었다. 초고속 통신망의 구축은 막대한 비용을 요구하기 때문에 망 구축비용의 감소를 위해서는 기존에 설치된 관로를 고려해야한다. 또한 초고속 통신망은 하나의 선로에 많은 양의 데이터가 전송되므로 한 선로에 문제가 있는 경우 막대한 손실이 발생하는 특징을 지닌다. 이 때문에 전체 네트워크를 일정수준이상의 생존도를 가질 수 있게 설계하여야한다. 이러한 문제의 해결을 위해서 기존의 논문에서는 비용을 줄이기 위해 고려된 기존 관로를 다음 단계에서 배제하여 한 관로를 여러 경로에서 사용함으로써 얻을 수 있는 비용 절감효과를 상실하였다. 그러나 본 논문에서는 생존도를 유지하는 범위 내에서 기존에 설치된 관로를 최대한 고려하여 비용 절감을 극대화한 네트워크를 효과적으로 설계하는 방법을 제안한다. 제안한 방법을 사용하여 실험한 결과에 따르면 기존의 방법에 비해 약 7%의 비용절감 효과를 얻을수 있었다.

A Robustness Analysis of Korea Expressway Network

Sung-Geun Lee(이성근),Chi-Geun Han(한치근) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.4

재난과 사고로 인해 고속도로 일부 구간이 폐쇄되는 경우가 발생한다. 이런 상황에서 고속도로망에 기능적으로 어떠한 상황이 발생하는지를 분석한다. 국내의 고속도로 망은 하나의 그래프로 표현할 수 있다. 고속도로의 일부 구간의 차단은 국가적인 재앙으로 번질 수 있다. 본 논문에서는 국내 고속도로 망의 강건성을 분석한다. 고속도로의 강건성은 일부 구간의 차단에 따라 국내 고속도로 망의 교통 통행 상황이 어느 정도 나빠지는지를 말한다. 강건성이 클수록 일부 차단의 효과가 작게 나타난다. 교통망의 하나의 구간의 혼잡도를 평가하기 위해 사용하는 방법으로 구간교통량(V)을 구간의 교통용량(C)으로 나누는 값을 사용한다. 본 연구는 국내 고속도로의 출발지점, 도착지점의 실제 교통량 데이터를 이용하여 고속도로의 강건성을 분석하고, 일부 차단에 따른 교통량의 변화를 실험계산을 통해 분석한다. 본 분석이 실제 국내 고속도로의 정확한 실상을 반영할 수는 없지만, 전체적인 망의 기초적인 강건성을 확인하는 목적으로 충분할 것으로 판단된다. Some sections of the highway are closed due to disasters and accidents. In this situation, it analyzes what kind of situation occurs due to functional failure in the highway network. The domestic highway network can be expressed as a graph. Blocking some sections of the highway can turn into a national disaster. In this paper, we analyze the robustness of the domestic highway network. The robustness of expressways refers to the degree to which the traffic conditions of the domestic expressway network deteriorate due to the blockage of some sections. The greater the robustness, the smaller the effect of some blocking appears. This study is used to evaluate the congestion level of one section of the transportation network, and a value obtained by dividing the section traffic volume (V) by the section traffic volume (C) is used. This study analyzes the robustness of highways by using the actual traffic volume data of the departure and arrival points of domestic highways, and analyzes the changes in traffic volume due to partial blockage through experimental calculations. Although this analysis cannot reflect the exact reality of domestic highways, it is judged to be sufficient for the purpose of confirming the basic robustness of the overall network.

무선 ATM 망에서 페이징 트래픽 부하의 감소를 위한 동적 페이징 영역 관리 기법

이태로,이성원,한치근,유인태,Lee, Tae-Ro,Lee, Seong-Won,Han, Chi-Geun,Yu, In-Tae 한국정보처리학회 2000 정보처리논문지 Vol.7 No.s8

본 논문은 ATM-Forum의 WATM 기반 제3세대 무선 멀티미디어 망 환경에서 하나의 M.E.SW(Mobility Enabled ATM Switch)가 단순화된 많은 AP들을 관리하는 방안에 대하여 고려하였다. 또한 WATM 망 환경에서 가변 그룹 크기와 동적인 그룹 페이징 순서 방법을 사용하는 효율적인 페이징 방안을 제안하였다. 그리고 제안한 방안과 기존의 방안에 대해 성능을 평가 및 분석하였다. 여기서는 blanket-polling, sequential-polling 그리고 고정크기 그룹화 방안과 같은 대부분의 기존 방안들을 제안한 가변적이면서 동적인 그룹화 방안과 비교 분석하였다. 분석결과 offered-load가 낮은 환경에서는 단순한 blanket-polling paging 방안이 약간 더 우수한 성능을 보였다. 그러나 트래픽 밀도가 높아지면서 제안한 방안이 기존의 방안들 보다 더 우수한 성능을 보였다. 성능개선은 주로 가변적인 그룹 크기와 MS(Mobile Station)기반 동적인 페이징 순서 방안에 기인한다. 또한 제안한 방안은 MS에 대한 아주 간단한 이력정보와 최종적으로 통신한 AP 정보만이 필요하다. 따라서 이 방안은 효율적으로 구현하는 것이 가능하다.

다중 제약이 있는 멀티캐스트 트리 문제에 관한 연구

이성근 ( Sung-geun Lee ),한치근 ( Chi-geun Han ) 한국인터넷정보학회 2004 인터넷정보학회논문지 Vol.5 No.5

스위치 노드(switch node)로 구성된 네트워크에서 멀티캐스팅을 위한 트리를 구성하는 것은 NP-complete로 알려진 스타이너 트리 문제(Steiner tree problem)로 정형화된다. 현재의 멀티캐스트를 요구하는 서비스들은 대개 대용량의 멀티미디어 데이터를 요구하게 된다. 이러한 서비스들은 텍스트 기반의 서비스에 비해 서비스의 질(Quality of Service)이 아주 중요한 요소가 되고, QoS는 전송에 소요되는 시간에 매우 민감하게 반응한다. 단일 제약을 갖는 멀티캐스트 트리 문제에 적용되는 휴리스틱은 이미 많이 연구되었으나, 노드 연결도 제한과 평균 홉수를 고려하는 다중 제약이 있는 멀티캐스트 트리 문제에 적용되는 휴리스틱에 대한 연구는 없었다. 본 논문에서는 다중 제약을 만족하는 효율적인 멀티캐스트 트리 문제에 적용 가능한 알고리즘을 제안하고, 실험을 통하여 성능을 평가하였다. In the telecommunications network, multicasting is widely used recently. Multicast tree problem is modeled as the NP-complete Steiner problem in the networks. In this paper, we study algorithms for finding efficient multicast trees with hop and node degree constraints. Multimedia service is an application of multicasting and it is required to transfer a large volume of multimedia data with QoS(Quality of Service). Though heuristics for solving the multicast tree problems with one constraint have been studied, however, there is no optimum algorithm that finds an optimum multicast tree with hop and node degree constraints up to now. In this paper, an approach for finding an efficient multicast tree that satisfies hop and node degree constraints is presented, and the experimental results explain how the hop and node degree constraints affect to the total cost of a multicast tree.