이발명을지원한국가연구개발사업 과제고유번호 NRF-2012M3C4A 부처명 미래창조과학부 연구관리전문기관 한국연구재단 연구사업명 차세대정보컴퓨팅기술개발사업 연구과제명 소셜및정보네트워크빅데이터마이닝소프트웨어원천기술개발 기여율 1/1 주관기관 서울대학교 연구기간

Size: px

Start display at page:

Download "이발명을지원한국가연구개발사업 과제고유번호 NRF-2012M3C4A 부처명 미래창조과학부 연구관리전문기관 한국연구재단 연구사업명 차세대정보컴퓨팅기술개발사업 연구과제명 소셜및정보네트워크빅데이터마이닝소프트웨어원천기술개발 기여율 1/1 주관기관 서울대학교 연구기간"

태성 국
6 years ago
Views:

1 (19) 대한민국특허청 (KR) (12) 공개특허공보 (A) (11) 공개번호 (43) 공개일자 2016년12월23일 (51) 국제특허분류 (Int. Cl.) H04L 12/24 ( ) (52) CPC 특허분류 H04L 41/12 ( ) H04L 41/142 ( ) (21) 출원번호 (22) 출원일자 2015 년 06 월 15 일 심사청구일자 전체청구항수 : 총 7 항 2015 년 06 월 15 일 (71) 출원인 한국과학기술원 대전광역시유성구대학로 291( 구성동 ) (72) 발명자 문수복 대전광역시유성구대학로 291, N1 608 ( 구성동 23, 한국과학기술원 ) 손윤규 대전광역시유성구대학로 291, N1 621 ( 구성동 23, 한국과학기술원 ) (74) 대리인 (54) 발명의명칭군집구조의교란정도를도출하는장치및방법 (57) 요약 제일특허법인 본발명의일실시예에따른군집구조교란정도도출장치는적어도두개이상의노드를포함하는원본군집구조에대한원본군집할당벡터와상기원본군집구조에서상기적어도두개이상의노드중어느하나인제 1 노드를제거한교란군집구조에대한교란군집할당벡터를생성하는벡터생성부, 상기원본군집구조가상기교란군집구조와차이가나는정도를나타내는상기원본군집구조에대한원본조건적엔트로피및상기교란군집구조가상기원본군집구조와차이가나는정도를나타내는상기교란군집구조에대한교란조건적엔트로피를생성하는조건적엔트로피생성부및상기원본조건적엔트로피와상기교란조건적엔트로피를기초로상기제 1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출하는인덱스도출부를포함할수있다. 대표도 - 도 3-1 -

2 이발명을지원한국가연구개발사업 과제고유번호 NRF-2012M3C4A 부처명 미래창조과학부 연구관리전문기관 한국연구재단 연구사업명 차세대정보컴퓨팅기술개발사업 연구과제명 소셜및정보네트워크빅데이터마이닝소프트웨어원천기술개발 기여율 1/1 주관기관 서울대학교 연구기간 ~

3 명세서청구범위청구항 1 적어도두개이상의노드를포함하는원본군집구조에대한원본군집할당벡터와상기원본군집구조에서상기적어도두개이상의노드중어느하나인제1 노드를제거한교란군집구조에대한교란군집할당벡터를생성하는벡터생성부 ; 상기원본군집구조가상기교란군집구조와차이가나는정도를나타내는상기원본군집구조에대한원본조건적엔트로피및상기교란군집구조가상기원본군집구조와차이가나는정도를나타내는상기교란군집구조에대한교란조건적엔트로피를생성하는조건적엔트로피생성부 ; 및상기원본조건적엔트로피와상기교란조건적엔트로피를기초로상기제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출하는인덱스도출부를포함하는군집구조의교란정도도출장치. 청구항 2 제 1 항에있어서, 상기원본군집구조가상기교란군집구조와차이가나는정도는, 상기교란군집구조를기준으로상기원본군집구조가상기교란군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하며, 상기교란군집구조가상기원본군집구조와차이가나는정도는, 상기원본군집구조를기준으로상기교란군집구조가상기원본군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하는군집구조의교란정도도출장치. 청구항 3 제 1 항에있어서, 상기인덱스도출부는, 상기원본조건적엔트로피와상기교란조건적엔트로피의합을상기교란군집구조를구성하는노드의수로나눈값을상기군집구조교란인덱스로도출하는군집구조의교란정도도출장치. 청구항 4 군집구조의교란정도도출장치에의한군집구조의교란정도를도출하는방법으로써, (a) 적어도두개이상의노드를포함하는원본군집구조에있어서, 상기노드가상기원본군집구조에속하는정도를나타내는제1 군집할당벡터를생성하는단계 ; (b) 상기원본군집구조를구성하는노드중어느하나인제1 노드를제거한군집구조인교란군집구조에대하여, 상기제1 노드를제외한나머지노드가상기교란군집구조에속하는정도를나타내는제2 군집할당벡터를생성하는단계 ; (c) 상기원본군집구조가상기교란군집구조와차이가나는정도를나타내는, 상기원본군집구조에대한원본조건적엔트로피를생성하는단계 ; - 3 -

4 (d) 상기교란군집구조가상기원본군집구조와차이가나는정도를나타내는, 상기교란군집구조에대한교란조건적엔트로피를생성하는단계 ; 및 (e) 상기원본조건적엔트로피와상기교란조건적엔트로피를기초로상기제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출하는단계를포함하는군집구조의교란정도를도출하는방법. 청구항 5 제 4 항에있어서, 상기 (c) 단계에서상기원본군집구조가상기교란군집구조와차이가나는정도는, 상기교란군집구조를기준으로상기원본군집구조가상기교란군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하며, 상기 (d) 단계에서상기교란군집구조가상기원본군집구조와차이가나는정도는, 상기원본군집구조를기준으로상기교란군집구조가상기원본군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하는군집구조의교란정도를도출하는방법. 청구항 6 제 4 항에있어서, 상기 (e) 단계는, 상기원본조건적엔트로피와상기교란조건적엔트로피의합을상기교란군집구조를구성하는노드의수로나눈값을상기군집구조교란인덱스로도출하는군집구조의교란정도를도출하는방법. 청구항 7 제 4 항내지제 6 항중어느한항의군집구조의교란정도를도출하는방법을수행하기위한컴퓨터프로그 램이기록된기록매체. 발명의설명 [0001] 기술분야본발명은군집구조의교란정도를도출하는장치및방법에관한것이며, 보다자세하게는군집구조를구성하는노드가제거되는경우이러한노드가해당군집구조에서갖는역할의유일한정도, 즉역할의유일도 (role uniqueness) 를고려하여군집구조의교란정도를나타내는군집구조교란인덱스를도출하는장치및방법에관한것이다. [0002] 배경기술사회, 기술또는자연계네트워크에서네트워크상의노드들은강한군집구조를보이는특성을갖는다. 이때, 군집구조는예를들면단백질이나세포네트워크등의기능적모듈에대응할수있다. 도 1은이러한군집구조를예시적으로나타낸도면이다. 도 1을참조하면중심이되는허브 (hub) 노드 (10, 20, 30) 가있고, 각허브노드 (10, 20, 30) 를중심으로이러한허브노드 (10, 20, 30) 와연결되는주변노드들 (11 내지 18, 21 내지 - 4 -

5 28, 31 내지 38) 이있다. [0003] [0004] [0005] 이와같은군집구조에서군집구조의유지는서버네트워크등의기술네트워크의효율적인운용을위해서매우중요한데, 군집구조의유지는군집구조를구성하는노드의역할 (role) 에대한중요성 (importance) 을정량화하는것에서부터시작한다. 이때, 노드의역할이란노드또는노드의집합이군집구조의유지에기여하는역할을의미한다. 노드의역할에대한중요성을정량화하는것과관련하여보다구체적으로살펴보면, 종래에는 2가지요소, 즉모듈내종속도 (within-module degree) 인 Z와참여계수 (participation coefficient) 인 P를기초로노드의역할에대한중요성을정량화하였다. 모듈내종속도 Z는특정클러스터가있을때이러한특정클러스터내의어느노드가해당특정클러스터내의다른노드들과연결되는정도를나타내는지표이며, 예를들면다음과같은수학식 1에의하여표현될수있다. 수학식 1 [0006] [0007] 여기서, Z i 는노드 i 가특정클러스터 S i 에서갖는모듈내종속도이며, κ i 는노드 i 가특정클러스터 S i 내의 다른노드들과연결되는정도의합 (sum of degree) 이고, (bar) κ si 는특정클러스터 S i 내의모든노드들에대하 여연산한 κ 값의평균이며, σ k_si 는특정클러스터 S i 내의모든노드들에대하여연산한 k 값의표준편차이다. [0008] 아울러, 참여계수 P 는특정클러스터가있을때이러한특정클러스터내의어느노드가특정클러스터가아닌 다른클러스터에속한노드들과의연결에대한가변성 (variability of connection) 을나타내는지표이며, 예를 들면다음과같은수학식 2 에의하여표현될수있다. 수학식 2 [0009] [0010] 여기서, P i 는노드 i 의참여계수이고, k i 는노드 i 가전체네트워크의다른노드들과연결된정도 (degree) 이며, κ is 는노드 i 가임의의클러스터 S 에속하는노드집합과연결된정도이다. 아울러, N M 은전체클러스터의개 수이고이때 S 는이러한전체클러스터중에서어느하나의클러스터를나타내는인덱스이다. [0011] [0012] [0013] 그런데, 전술한 2가지요소를기초로노드의역할을정량화하는방법에서는노드의역할에대한유일한정도, 즉역할의유일도 (uniqueness) 는고려하지않는다. 따라서노드가제거되거나이러한노드에장애가발생하였을때해당군집구조가겪게되는교란 ( 또는변화 ) 를예측할수없다. 역할의유일도를고려하지않는이러한종래의방법을이용하여노드의역할을정량화한예를살펴보면, 도 2a 에서허브노드 (40) 는주변노드 (41 내지 48) 와연결되어있으므로허브노드 (40) 의모듈내종속도는주변노드 (41 내지 48) 보다높은값을갖는다. 도 2b에서허브노드 (50) 와또다른허브노드 (51) 도마찬가지로도 2a 와같이모듈내종속도가높은값을갖는다. 아울러, 참여계수의경우도 2a와 2b에서는 1개의클러스터만도시되어있으므로모두 0인값을갖는다. 이때, 도 2a에서허브노드 (40) 가제거되는경우도 2a의군집구조는 8개의개별적인군집구조로나뉘어진다. 즉, 도 2a의군집구조에서허브노드 (40) 의역할은유일하므로, 이러한허브노드 (40) 의제거는군집구조에큰변화를발생시킨다. 이는, 허브노드 (40) 는군집구조의유지에있어서상대적으로중요한역 - 5 -

6 할을하고있다고할수있다. [0014] [0015] [0016] [0017] 반면, 도 2b에서허브노드 (50) 가제거되는경우, 제거된허브노드 (50) 와동일한연결을갖는또다른허브노드 (51) 에의하여여전히 1개의군집구조가유지된다. 즉, 도 2b의군집구조에서허브노드 (50) 의역할은또다른허브노드 (51) 의역할과중복되므로유일하지않으며, 이러한허브노드 (50) 의제거는군집구조에큰변화를발생시키지않는다. 즉, 허브노드 (50) 는군집구조의유지에있어서상대적으로중요한역할을하고있지는않는다고할수있다. 그럼에도불구하고종래의방법에따라서도 2a의허브노드 (40) 와도 2b의허브노드 (50) 에대한역할의중요성을정량화한결과는거의동일하다. 이는종래의방법은노드에대한역할의유일도를고려하지않기때문이다. 그런데, 노드에대한역할의유일도를고려하고이를토대로노드가제거되거나노드에장애가발생하였을때군집구조에일어나는변화를예측하는것은다음과같은분야에서다양하게활용될수있다. 예를들면, 대규모온라인네트워크, 테러조직간의사회네트워크상에서각하위네트워크의응집구조가어떠한노드가제거되었을때가장큰변화를겪게되는지를사전에예측할수있다. 또한, MRI나 DFI 등의두뇌신경네트워크를통해얻은두뇌모듈들간의연결정보를통하여어떤모듈에장애가발생하였을때두뇌기능네트워크에가장큰충격을줄수있는지를사전에예측할수있다. 뿐만아니라, 통신네트워크에서개별행위자의가격 / 가치결정메커니즘의하나로이용될수도있으며, 전력망과부하상황등과같이사회기반네트워크시설재난상황에서의전체네트워크구조변화예측에도움을줄수있다. 이를토대로살펴보면, 노드의역할에대한중요성을정량화함에있어서노드에대한역할의유일도를고려하는방법이요구된다고할수있다. 선행기술문헌 [0018] 특허문헌 ( 특허문헌 0001) 한국공개특허공보, ( 공개 ) 발명의내용 [0019] [0020] 해결하려는과제본발명의해결하고자하는과제는노드의역할의유일도 (role uniqueness) 를고려하여노드의역할의중요성을정량화하는장치및방법을제공하는것이다. 다만, 본발명의해결하고자하는과제는이상에서언급한것으로제한되지않으며, 언급되지않은또다른해결하고자하는과제는아래의기재로부터본발명이속하는통상의지식을가진자에게명확하게이해될수있을것이다. [0021] [0022] 과제의해결수단본발명의일실시예에따른군집구조교란정도도출장치는적어도두개이상의노드를포함하는원본군집구조에대한원본군집할당벡터와상기원본군집구조에서상기적어도두개이상의노드중어느하나인제1 노드를제거한교란군집구조에대한교란군집할당벡터를생성하는벡터생성부, 상기원본군집구조가상기교란군집구조와차이가나는정도를나타내는상기원본군집구조에대한원본조건적엔트로피및상기교란군집구조가상기원본군집구조와차이가나는정도를나타내는상기교란군집구조에대한교란조건적엔트로피를생성하는조건적엔트로피생성부및상기원본조건적엔트로피와상기교란조건적엔트로피를기초로상기제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출하는인덱스도출부를포함할수있다. 또한, 상기원본군집구조가상기교란군집구조와차이가나는정도는, 상기교란군집구조를기준으로상 - 6 -

7 기원본군집구조가상기교란군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하며, 상기교란군집구조가상기원본군집구조와차이가나는정도는, 상기원본군집구조를기준으로상기교란 군집구조가상기원본군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로할수있다. [0023] [0024] [0025] [0026] [0027] 또한, 상기인덱스도출부는상기원본조건적엔트로피와상기교란조건적엔트로피의합을상기교란군집구조를구성하는노드의수로나눈값을상기군집구조교란인덱스로도출할수있다. 본발명의다른실시예에따른군집구조교란정도를도출하는방법은 (a) 적어도두개이상의노드를포함하는원본군집구조에있어서, 상기노드가상기원본군집구조에속하는정도를나타내는제1 군집할당벡터를생성하는단계, (b) 상기원본군집구조를구성하는노드중어느하나인제1 노드를제거한군집구조인교란군집구조에대하여, 상기제1 노드를제외한나머지노드가상기교란군집구조에속하는정도를나타내는제2 군집할당벡터를생성하는단계, (c) 상기원본군집구조가상기교란군집구조와차이가나는정도를나타내는, 상기원본군집구조에대한원본조건적엔트로피를생성하는단계, (d) 상기교란군집구조가상기원본군집구조와차이가나는정도를나타내는, 상기교란군집구조에대한교란조건적엔트로피를생성하는단계및 (e) 상기원본조건적엔트로피와상기교란조건적엔트로피를기초로상기제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출하는단계를포함할수있다. 또한, 상기 (c) 단계에서상기원본군집구조가상기교란군집구조와차이가나는정도는, 상기교란군집구조를기준으로상기원본군집구조가상기교란군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로하며, 상기 (d) 단계에서상기교란군집구조가상기원본군집구조와차이가나는정도는, 상기원본군집구조를기준으로상기교란군집구조가상기원본군집구조와갖는구조상의차이를나타내는정보의양인것을특징으로할수있다. 또한, 상기 (e) 단계는상기원본조건적엔트로피와상기교란조건적엔트로피의합을상기교란군집구조를구성하는노드의수로나눈값을상기군집구조교란인덱스로도출할수있다. 본발명의또다른측면에따르면, 군집구조의교란정도를도출하는방법은이러한방법을수행하기위한컴퓨터프로그램이기록된기록매체에구현될수있다. [0028] 발명의효과본발명의일실시예에따르면, 노드의역할의유일도 (role uniqueness) 를고려하여노드의역할의중요성을정량화할수있다. 따라서, 대규모온라인네트워크, 테러조직간의사회네트워크상에서각하위네트워크의응집구조가어떠한노드가제거되었을때가장큰변화를겪게되는지를사전에예측할수있다. 또한, MRI나 DFI 등의두뇌신경네트워크를통해얻은두뇌모듈들간의연결정보를통하여어떤모듈에장애가발생하였을때두뇌기능네트워크에가장큰충격을줄수있는지를사전에예측할수있다. 뿐만아니라, 통신네트워크에서개별행위자의가격 / 가치결졍메커니즘의하나로이용될수도있으며, 전력망과부하상황등과같이사회기반네트워크시설재난상황에서의전체네트워크구조변화예측에도움을줄수있다. [0029] 도면의간단한설명 도 1 은적어도두개이상의노드에의하여구성된군집구조를예시적으로나타낸도면이다. 도 2a 및 2b는군집구조를예시적으로나타낸도면이다. 도 3은본발명의일실시예에따른군집구조의교란정도도출장치의구성을예시적으로도시한도면이다. 도 4는본발명의일실시예에따른군집구조의교란정도를도출하는방법의절차를예시적으로도시한도면이다. 도 5a 및 5b는군집구조에서노드가제거되기전과제거된후를예시적으로나타낸도면이다. 도 6a 및 6b는군집구조에서노드가제거되기전과제거된후를예시적으로나타낸도면이다. 발명을실시하기위한구체적인내용 - 7 -

8 [0030] [0031] [0032] [0033] [0034] [0035] [0036] [0037] 본발명의이점및특징, 그리고그것들을달성하는방법은첨부되는도면과함께상세하게후술되어있는실시예들을참조하면명확해질것이다. 그러나본발명은이하에서개시되는실시예들에한정되는것이아니라서로다른다양한형태로구현될수있으며, 단지본실시예들은본발명의개시가완전하도록하고, 본발명이속하는기술분야에서통상의지식을가진자에게발명의범주를완전하게알려주기위해제공되는것이며, 본발명은청구항의범주에의해정의될뿐이다. 본발명의실시예들을설명함에있어서공지기능또는구성에대한구체적인설명이본발명의요지를불필요하게흐릴수있다고판단되는경우에는그상세한설명을생략할것이다. 그리고후술되는용어들은본발명의실시예에서의기능을고려하여정의된용어들로서이는사용자, 운용자의의도또는관례등에따라달라질수있다. 그러므로그정의는본명세서전반에걸친내용을토대로내려져야할것이다. 도 3은본발명의일실시예에따른군집구조의교란정도도출장치의구성을예시적으로도시한도면이다. 먼저, 군집구조의교란정도도출장치 ( 이하교란정도도출장치라고지칭하기로함 )(100) 는적어도일부의소프트웨어와하드웨어의하이브리드구현방식으로, 프로세서및프로세서에의해실행되는명령어들을저장하는메모리를포함하는전자디바이스또는컴퓨터프로그램에의해선택적으로활성화또는재구성되는프로그래밍가능한머신 (machine) 상에서구현될수있다. 또한, 본발명의일실시예에서제시하는특징들및 / 또는기능성들중적어도일부는최종사용자컴퓨터시스템, 컴퓨터, 네트워크서버또는서버시스템, 모바일컴퓨팅디바이스 ( 예를들어, PDA(personal digitalassistant), 모바일전화기, 스마트폰, 랩탑, 태블릿컴퓨터또는그와유사한것 ), 소비자전자디바이스, 또는임의의다른적합한전자디바이스또는그들의임의의조합과같은하나이상의범용네트워크호스트머신에서등에서구현될수있다. 도 3을참조하면, 교란정도도출장치 (100) 는입력부 (120), 벡터생성부 (140), 조건적엔트로피생성부 (160) 및인덱스도출부 (180) 를포함할수있다. 다만, 이는일실시예에따른것이므로이중적어도하나이상의구성을포함하지않거나또는이외의다른구성을더포함할수도있다. 입력부 (120) 는군집구조에대한데이터를입력받을수있으며, 예를들면컴퓨터와같은연산장치에서파일에저장된데이터를읽어들이는구성일수있다. 입력부 (120) 를통해입력되는군집구조에대한데이터는다양한포맷 (format) 일수있다. 여기서, 입력부 (120) 에대한자세한구성또는군집구조에대한데이터의포맷은관련분야에서당업자에게자명한가상이므로구체적인설명은생략하기로한다. 벡터생성부 (140) 는군집구조에대한군집할당벡터를생성하며, 예를들면컴퓨터와같은연산장치에서구현될수있다. 군집할당벡터는네트워크상의노드가군집구조에포함되는지를나타내는벡터이며, 다음과같은수학식 3에의하여생성된다. 수학식 3 [0038] [0039] 여기서, s 는전체 m 개의클러스터중임의의한개의클러스터를지칭하는인덱스이며, l s 는클러스터 s 내에속 한연결 ( 링크 ) 의개수이고, L은전체네트워크에속한링크 ( 연결 ) 의개수이며, d s 는클러스터 s에속한전체노드의연결도 (degree) 애대한합이다. 아울러, 군집할당벡터를생성하는것은비특허문헌 Newman, M. and M.Girvan(2004), "Finding and evaluating community structure in networks." Physical review.e, Statistical, nonlinear, and soft matter physics 69(2 Pt 2): 에서기술하고있으므로이에관한보다자세한설명은생략하기로한다. [0040] [0041] 일실시예에따르면벡터생성부는 (140) 는원본군집구조에대한원본군집할당벡터를생성한다. 원본군집 구조란적어도 2 개이상의노드를포함하는군집구조를의미한다. 아울러, 벡터생성부 (140) 는교란군집구조에대한교란군집할당벡터를생성한다. 교란군집구조란원본 - 8 -

9 군집구조에포함된노드중에서어느하나의노드인제 1 노드를제거한군집구조를의미한다. [0042] [0043] [0044] [0045] [0046] 여기서, 교란군집구조는원본군집구조에포함된노드중에서어느하나가아닌적어도 2개이상의노드를제거한군집구조를의미할수도있으며, 이경우벡터생성부 (140) 는이와같이원본군집구조에서적어도 2 개이상의노드를제거한교란군집구조에대한교란군집할당벡터를생성할수도있다. 조건적엔트로피생성부 (160) 는원본군집구조와교란군집구조에대한조건적엔트로피를생성하며, 예를들면컴퓨터와같은연산장치에서구현될수있다. 보다구체적으로살펴보면, 조건적엔트로피생성부 (160) 는원본군집할당벡터와교란군집할당벡터를기초로원본군집할당벡터에대한원본조건적엔트로피를생성한다. 여기서, 원본조건적엔트로피는교란군집구조를기준으로원본군집구조를설명하기위하여추가적으로필요한정보의양을의미할수있으며, 다만이는예시적인것이므로이에한정되지는않는다. 아울러, 조건적엔트로피생성부 (160) 는원본군집할당벡터와교란군집할당벡터를기초로교란군집할당벡터에대한교란조건적엔트로피를생성한다. 여기서, 교란조건적엔트로피는원본군집구조를기준으로교란군집구조를설명하기위하여추가적으로필요한정보의양을의미할수있으며, 다만이는예시적인것이므로이에한정되지는않는다. 일실시예에서, 조건적엔트로피생성부 (160) 는원본군집구조와교란군집구조에대한조건적엔트로피를다음의같은수학식 4에의하여생성할수있다. 수학식 4 [0047] [0048] [0049] [0050] [0051] [0052] [0053] [0054] 여기서, 함수 H(X Y) 는조건적엔트로피를도출하며구체적으로는 Y를기초로 X를추론할때필요한정보의양또는불확정성을의미하며, 그에대한보다자세한식은가장우변에기술하였다. 여기서이러한함수 H 및가장우변의식에의하여조건적엔트로피를생성하는기술그자체는비특허문헌 Karrer, B., E. Levina, et al. (2008). "Robustness of community structure in networks." Physical Review E 77(4) 와 Meila, M. (2007). "Comparing clusterings - an information based distance." Journal of Multivariate Analysis 98(5): 에서이미개시하고있는기술이므로이에관한자세한설명은생략하기로한다. 또한, C는원본군집구조를나타내고, C' 는교란군집구조를나타낸다. 따라서, H(C C') 은교란군집구조를기초로원본군집구조를설명하기위하여추가적으로필요한정보의양을의미하고, H(C' C) 는원본군집구조를기초로교란군집구조를설명하기위하여추가적으로필요한정보의양을의미한다. 이를기초로살펴보면, 조건적엔트로피생성부 (160) 가생성한조건적엔트로피의값이크다는것은원본군집구조와교란군집구조사이에구조적인차이가크다는것을의미한다. 즉, 해당노드가제거되거나해당노드에장애가발생하면이러한노드를포함하는군집구조에큰변화가발생될수있음을의미한다. 반면, 조건적엔트로피의값이작다는것은원본군집구조와교란군집구조사이에구조적인차이가적다는것을의미한다. 즉, 해당노드가제거되거나해당노드에장애가발생하더라도해당노드와동일또는유사한역할을하는노드가존재하므로이러한노드를포함하는군집구조에큰변화가발생되지않음을의미한다. 여기서, 일실시예에따르는경우, 원본군집구조에 N개의노드가포함되어있다고가정하면조건적엔트로피의값은예를들면최대 logn에서최소 0의값을가질수있다. 인덱스도출부 (180) 는군집구조에포함된노드에대한군집구조교란인덱스 (Community structure Perturbation Index, CPI) 를도출하며, 예를들면컴퓨터와같은연산장치에서구현될수있다. 군집구조교란인덱스는노드의역할의유일성을나타내는지표이며, 따라서노드의제거에의한교란정도를나타내는지표일수있다. 보다구체적으로살펴보면, 인덱스도출부 (180) 는조건적엔트로피생성부 (160) 가생성한원본조건적엔트로피와교란조건적엔트로피를기초로제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도 - 9 -

10 출한다. 이때, 인덱스도출부 (180) 는원본조건적엔트로피와교란조건적엔트로피를합하고이러한합을교 란군집구조를구성하는노드의수로나눌수있으며, 이와같이나눈값을군집구조교란인덱스로도출할 수있고, 이는다음과같은수학식 5 에의하여표현될수있다. 수학식 5 [0055] [0056] [0057] 여기서, CPI i 는 i 번째노드의군집구조교란인덱스를나타낸다. 또한, N 은원본군집구조에포함된노드의개수또는노드의집합의개수를의미 ( N 개 ) 하며, g 는전체링크 집합을의미하고, C(N,g) 는원본네트워크의군집구조를의미하며, C i 는원본네트워크상에서노드 i 에대응 하는원본할당벡터요소를의미한다. 아울러, 역슬래쉬 '\' 는제거의연산자로정의하면 C(N,g)\C i 는원본 할당벡터요소에서 C i 를제거한요소를의미한다. [0058] 여기서군집구조교란인덱스는전술한바와같이노드 i가제거되기전의원본군집구조와노드 i가제거된후의교란군집구조를비교하는것이므로함수 V의첫번째인자는노드 i가제거되기전의원본군집구조에관한것이어야한다. 그러나, 함수 V에서원본군집구조와교란군집구조를비교하기위해서는노드의수, 즉노드의차원이동일해야하므로위의식에서 C(N,g) 를구한뒤계산을위하여 C i 를제거한인자를함수 V의 첫번째인자로집어넣은것이다. 즉, 함수 V 의첫번째인자는계산의측면에서 C i 를제거한인자로표현된것 일뿐실질적으로는노드 i 가제거되기전의원본군집구조에관한것이다. [0059] 아울러, g i 는노드 i 가속한링크의집합을의미하며, C(N/i, g/g i ) 는원본군집구조에서 i 번째노드와그에연 결된링크 ( 연결 ) 집합 gi 를제거한네트워크의군집구조, 즉교란군집구조에대한교란할당벡터를의미한 다. [0060] [0061] [0062] [0063] [0064] [0065] [0066] 따라서, 수학식 5에따라도출된군집구조교란인덱스를이용하면어느노드에대한역할유일성을도출할수있으므로해당노드가제거되거나해당노드에장애가발생하였을때군집구조에미치는영향을정량화할수있다. 아울러, 수학식 5에서와같이이러한군집구조교란인덱스는정규화 (log N -1에의하여 ) 되어있으므로보다용이하게이러한인덱스의크기를인식할수있다. 이하, 본발명의일실시예에따른작용과효과를살펴보기로한다. 도 4는본발명의일실시예에따른군집구조의교란정도를도출하는방법의절차를예시적으로도시한도면으로, 이러한군집구조의교란정도를도출하는방법은도 3에도시된교란정도도출장치 (100) 에의하여수행될수있다. 도 4를참조하면, 적어도두개이상의노드를포함하는원본군집구조에있어서이러한노드가원본군집구조에속하는정도를나타내는제1 군집할당벡터를생성하는단계는벡터생성부 (140) 에의하여수행될수있다 (S110). 다음으로, 교란군집구조에대한교란군집할당벡터를생성하는단계가수행되며이러한단계는벡터생성부 (140) 에의하여수행될수있다 (S120). 교란군집구조란원본군집구조에포함된노드중에서어느하나의노드인제1 노드를제거한군집구조또는원본군집구조에포함된노드중에서어느하나가아닌적어도 2개이상의노드를제거한군집구조를의미할수도있음은전술한바와같다. 다음으로, 원본군집구조에대한조건적엔트로피를생성하는단계가수행되며이러한단계는조건적엔트로피생성부 (160) 에의하여수행될수있다 (S130). 보다구체적으로살펴보면, 조건적엔트로피생성부 (160) 는원본군집할당벡터와교란군집할당벡터를기초로원본군집할당벡터에대한원본조건적엔트로피를생성한다. 여기서, 원본조건적엔트로피는교란군집구조를기준으로원본군집구조를설명하기위하여추가적으로필요한정보의양을의미할수있으며, 다만이

11 는예시적인것이므로이에한정되지는않는다. [0067] [0068] [0069] [0070] [0071] [0072] [0073] [0074] [0075] [0076] [0077] [0078] [0079] 다음으로, 교란군집구조에대한조건적엔트로피를생성하는단계가수행되며이러한단계는조건적엔트로피생성부 (160) 에의하여수행될수있다 (S140). 보다구체적으로살펴보면, 조건적엔트로피생성부 (160) 는원본군집할당벡터와교란군집할당벡터를기초로교란군집할당벡터에대한교란조건적엔트로피를생성한다. 여기서, 교란조건적엔트로피는원본군집구조를기준으로교란군집구조를설명하기위하여추가적으로필요한정보의양을의미할수있으며, 다만이는예시적인것이므로이에한정되지는않는다. 이를기초로살펴보면, 조건적엔트로피의값이크다는것은원본군집구조와교란군집구조사이에구조적인차이가크다는것을의미한다. 즉, 해당노드가제거되거나해당노드에장애가발생하면이러한노드를포함하는군집구조에큰변화가발생될수있음을의미한다. 반면, 조건적엔트로피의값이작다는것은원본군집구조와교란군집구조사이에구조적인차이가적다는것을의미한다. 즉, 해당노드가제거되거나해당노드에장애가발생하더라도해당노드와동일또는유사한역할을하는노드가존재하므로이러한노드를포함하는군집구조에큰변화가발생되지않음을의미한다. 여기서, 일실시예에따르는경우, 원본군집구조에 N개의노드가포함되어있다고가정하면조건적엔트로피의값은예를들면최대 logn에서최소 0의값을가질수있다. 다음으로, 군집구조교란인덱스를도출하는단계가수행되며이는인덱스도출부 (180) 에의하여수행될수있다. 군집구조교란인덱스는노드의역할의유일성을나타내는지표이며, 따라서노드의제거에의한교란정도를나타내는지표일수있다. 보다구체적으로살펴보면, 인덱스도출부 (180) 는조건적엔트로피생성부 (160) 가생성한원본조건적엔트로피와교란조건적엔트로피를기초로제1 노드의제거에의한교란정도를나타내는군집구조교란인덱스를도출한다. 이때, 인덱스도출부 (180) 는원본조건적엔트로피와교란조건적엔트로피를합하고이러한합을교란군집구조를구성하는노드의수로나눌수있으며, 이와같이나눈값을군집구조교란인덱스로도출할수있다. 따라서, 이러한군집구조교란인덱스를이용하면어느노드에대한역할유일성을도출할수있으므로해당노드가제거되거나해당노드에장애가발생하였을때군집구조에미치는영향을정량화할수있다. 아울러, 군집구조교란인덱스는정규화 (log N -1에의하여 ) 되어있으므로보다용이하게이러한인덱스의크기를인식할수있다. 이상에서살펴본바와같이, 본발명의일실시예에따르면어느노드에대한역할유일성을도출할수있으므로해당노드가제거되거나해당노드에장애가발생하였을때군집구조에미치는영향을정량화할수있다. 아울러, 군집구조교란인덱스는정규화 (log N -1에의하여 ) 되어있으므로보다용이하게이러한인덱스의크기를인식할수있다. 도 5a 및 5b와도 6a 및 6b는군집구조에서노드가제거되기전과제거된후를예시적으로나타낸도면이다. 도 5a에도시된허브노드 (40) 가제거되는경우도 5a의군집구조 (49) 는도 5b에도시된것과같이 8개의군집구조 ( 주변노드 1개마다하나의군집구조 ) 로나뉘어진다. 즉, 도 5a의군집구조에서허브노드 (40) 의역할은유일하므로, 이러한허브노드 (40) 의제거는군집구조에큰변화를발생시킨다. 즉, 허브노드 (40) 의군집구조교란인덱스는상대적으로높은값을가진다. 수학식 5를참고하여살펴보면, N은 9이고, log 8은 3이며, g(40) 는 (40,41),(40,42),..., (40,47),(40,48)} 이다. 따라서, H(C C') 은 1.5인값을가지고 H(C' C) 는 1.5 인값을가지므로최종적으로허브노드 (40) 의군집구조교란인덱스의값은 1이다. 즉, 도 5a의원본군집구조에서도 5b의교란군집구조를설명하기위하여필요한추가적인정보는확률분포와결합확률분포벡터에의하여정의되며, 허브노드 (40) 을제외한할당벡터성분을 Cx, C'x라고하면, 각각의벡터는 P(Cx) = (1), P(C'x) = (1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8), P(Cx,C'x) = (1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8) 이다. 이를수학식 4와수학식 5에대입하면군집구조교란인덱스는 1의값을갖는다. 반면, 도 6a의경우허브노드 (60) 과이에연결된주변노드들 (61 내지 64) 이하나의군집구조 (71) 를형성하며허브노드 (70) 과이에연결된주변노드들 (65 내지 68) 이또하나의군집구조 (72) 를형성한다. 즉, 2개의군

12 집구조를형성한다. [0080] [0081] [0082] [0083] [0084] [0085] [0086] 이때, 허브노드 (60) 가제거되는경우도 6a의군집구조는도 6b에도시된것과같이 2개의군집구조에서 1 개의군집구조로합쳐질뿐 (merged), 도 5b와같이각각 8개의군집구조로나눠지지않는다. 즉, 도 2b의군집구조에서허브노드 (50) 의역할은또다른허브노드 (51) 의역할과중복되어유일하지않으며, 이러한허브노드 (50) 의제거는군집구조에큰변화를발생시키지않는다. 즉, 허브노드 (60) 의군집구조교란인덱스는상대적으로낮은값을가진다. 수학식 5를참고하여살펴보면, N 은 10이고, log 9는 3.17이며, H(C C') 은 0인값을가지고 H(C' C) 는 0인값을가지므로, 최종적으로허브노드 (60) 와허브노드 (70) 의군집구조교란인덱스의값은 0이다. 즉, 도 6a의원본군집구조에서도 6b의교란군집구조를설명하기위하여필요한추가적인정보는확률분포와결합확률분포벡터에의하여정의되며, 허브노드 (60) 을제외한할당벡터성분을 Cx, C'x라고하면, 각각의벡터는 P(Cx) = (1), P(C'x) = (1), P(Cx,C'x) = (1) 이다. 이를수학식 4와수학식 5에대입하면군집구조교란인덱스는 0의값을갖는다. 이를토대로살펴보면, 노드의역할의유일성에따라서군집구조교란인덱스의값이달리짐을알수있다. 한편, 본발명의일실시예에따른군집구조의교란지표를도출하는방법은컴퓨터프로그램이기록된기록매체에구현될수있다. 본발명에첨부된블록도의각블록과흐름도의각단계의조합들은컴퓨터프로그램인스트럭션들에의해수행될수도있다. 이들컴퓨터프로그램인스트럭션들은범용컴퓨터, 특수용컴퓨터또는기타프로그램가능한데이터프로세싱장비의프로세서에탑재될수있으므로, 컴퓨터또는기타프로그램가능한데이터프로세싱장비의프로세서를통해수행되는그인스트럭션들이블록도의각블록또는흐름도의각단계에서설명된기능들을수행하는수단을생성하게된다. 이들컴퓨터프로그램인스트럭션들은특정방식으로기능을구현하기위해컴퓨터또는기타프로그램가능한데이터프로세싱장비를지향할수있는컴퓨터이용가능또는컴퓨터판독가능메모리에저장되는것도가능하므로, 그컴퓨터이용가능또는컴퓨터판독가능메모리에저장된인스트럭션들은블록도의각블록또는흐름도각단계에서설명된기능을수행하는인스트럭션수단을내포하는제조품목을생산하는것도가능하다. 컴퓨터프로그램인스트럭션들은컴퓨터또는기타프로그램가능한데이터프로세싱장비상에탑재되는것도가능하므로, 컴퓨터또는기타프로그램가능한데이터프로세싱장비상에서일련의동작단계들이수행되어컴퓨터로실행되는프로세스를생성해서컴퓨터또는기타프로그램가능한데이터프로세싱장비를수행하는인스트럭션들은블록도의각블록및흐름도의각단계에서설명된기능들을실행하기위한단계들을제공하는것도가능하다. 또한, 각블록또는각단계는특정된논리적기능 ( 들 ) 을실행하기위한하나이상의실행가능한인스트럭션들을포함하는모듈, 세그먼트또는코드의일부를나타낼수있다. 또, 몇가지대체실시예들에서는블록들또는단계들에서언급된기능들이순서를벗어나서발생하는것도가능함을주목해야한다. 예컨대, 잇달아도시되어있는두개의블록들또는단계들은사실실질적으로동시에수행되는것도가능하고또는그블록들또는단계들이때때로해당하는기능에따라역순으로수행되는것도가능하다. 이상의설명은본발명의기술사상을예시적으로설명한것에불과한것으로서, 본발명이속하는기술분야에서통상의지식을가진자라면본발명의본질적인특성에서벗어나지않는범위에서다양한수정및변형이가능할것이다. 따라서, 본발명에개시된실시예들은본발명의기술사상을한정하기위한것이아니라설명하기위한것이고, 이러한실시예에의하여본발명의기술사상의범위가한정되는것은아니다. 본발명의보호범위는아래의청구범위에의하여해석되어야하며, 그와동등한범위내에있는모든기술사상은본발명의권리범위에포함되는것으로해석되어야할것이다. [0087] 부호의설명 100: 군집구조교란정도도출장치 120: 입력부 140: 벡터생성부 160: 조건적엔트로피생성부

13 180: 인덱스도출부 도면 도면 1 도면 2a

14 도면 2b 도면

15 도면 4 도면 5a 도면 5b

16 도면 6a 도면 6b

비휘발성메모리의맵핑정보, 및상기맵핑정보가저장된시점에서할당된제 1 물리블록주소를상기비휘발성메모리에저장하는맵핑정보저장모듈 ; 상기제 1 물리블록주소로부터현재할당된제 2 물리블록주소까지스캔을수행하는스캔모듈 ; 및 상기스캔결과에따라상기제 1 물리블록주소및상기제 2 물리블록주소

비휘발성메모리의맵핑정보, 및상기맵핑정보가저장된시점에서할당된제 1 물리블록주소를상기비휘발성메모리에저장하는맵핑정보저장모듈 ; 상기제 1 물리블록주소로부터현재할당된제 2 물리블록주소까지스캔을수행하는스캔모듈 ; 및 상기스캔결과에따라상기제 1 물리블록주소및상기제 2 물리블록주소 (19) 대한민국특허청 (KR) (12) 공개특허공보 (A) (51) Int. Cl. G06F 12/16 (2006.01) G06F 12/00 (2006.01) (11) 공개번호 (43) 공개일자 10-2007-0088102 2007 년 08 월 29 일 (21) 출원번호 10-2006-0018286 (22) 출원일자 2006년02월24일 심사청구일자 2006년02월24일