1 |
1
전자 장치의 동작 방법에 있어서, 대규모 그래프로부터 요약되는 요약 그래프 및 상기 대규모 그래프와 상기 요약 그래프 간 차이를 나타내는 교정 정보를 저장하는 동작; 상기 대규모 그래프에서 변경 엣지를 검출하는 동작; 상기 변경 엣지에 기반하여, 상기 변경 엣지에 의해 연결되는 변경 노드들을 검출하는 동작; 및상기 변경 노드들의 각각에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작을 포함하는 방법
|
2 |
2
제 1 항에 있어서, 상기 요약 그래프는,상기 대규모 그래프로부터 검출되는 복수 개의 노드들과 상기 노드들을 연결하는 엣지들로부터 요약되는 적어도 하나의 슈퍼 노드와 상기 슈퍼 노드를 연결하는 적어도 하나의 슈퍼 엣지로 이루어지는 방법
|
3 |
3
제 2 항에 있어서, 상기 변경 엣지는,상기 대규모 그래프에 추가되는 엣지 또는 상기 대규모 그래프로부터 삭제되는 엣지 중 적어도 하나를 포함하는 방법
|
4 |
4
제 2 항에 있어서, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작은,상기 변경 노드들의 각각의 적어도 하나의 인접 노드를 위한 슈퍼 노드의 변경 여부를 결정하는 동작; 및상기 인접 노드를 위한 슈퍼 노드의 변경에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작을 포함하는 방법
|
5 |
5
제 4 항에 있어서, 상기 인접 노드를 위한 슈퍼 노드의 변경 여부를 결정하는 동작은, 코스(coarse) 클러스터들을 업데이트하는 동작; 상기 변경 노드들의 각각에 대해, 무작위로 선택되는 정해진 개수의 인접 노드들로 테스팅 풀을 구성하는 동작; 상기 테스팅 풀의 일부를 테스팅 노드로 결정하는 동작; 및상기 테스팅 노드에 대한 테스팅을 통해, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작을 포함하는 방법
|
6 |
6
제 5 항에 있어서, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작은,상기 테스팅 노드를 포함하는 코스 클러스터를 확인하는 동작; 상기 테스팅 풀과 상기 코스 클러스터에 공동으로 속하는 노드들로 후보 풀을 구성하는 동작;상기 후보 풀로부터 후보 노드를 선택하는 동작; 상기 테스팅 노드에 대해 상기 후보 노드의 슈퍼 노드로의 이동에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하는 동작; 및상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하는 동작을 포함하는 방법
|
7 |
7
제 5 항에 있어서, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작은,상기 테스팅 노드에 대해 단독 슈퍼 노드로의 생성에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하는 동작; 및상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하는 동작을 포함하는 방법
|
8 |
8
컴퓨터 장치에 결합되어, 상기 컴퓨터 장치에 의해 판독 가능한 기록 매체에 저장된 컴퓨터 프로그램에 있어서, 대규모 그래프로부터 요약되는 요약 그래프 및 상기 대규모 그래프와 상기 요약 그래프 간 차이를 나타내는 교정 정보를 저장하는 동작; 상기 대규모 그래프에서 변경 엣지를 검출하는 동작; 상기 변경 엣지에 기반하여, 상기 변경 엣지에 의해 연결되는 변경 노드들을 검출하는 동작; 및상기 변경 노드들의 각각에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작을 실행하기 위한 컴퓨터 프로그램
|
9 |
9
제 8 항에 있어서, 상기 요약 그래프는,상기 대규모 그래프로부터 검출되는 복수 개의 노드들과 상기 노드들을 연결하는 엣지들로부터 요약되는 적어도 하나의 슈퍼 노드와 상기 슈퍼 노드를 연결하는 적어도 하나의 슈퍼 엣지로 이루어지는 컴퓨터 프로그램
|
10 |
10
제 9 항에 있어서, 상기 변경 엣지는,상기 대규모 그래프에 추가되는 엣지 또는 상기 대규모 그래프로부터 삭제되는 엣지 중 적어도 하나를 포함하는 컴퓨터 프로그램
|
11 |
11
제 9 항에 있어서, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작은,상기 변경 노드들의 각각의 적어도 하나의 인접 노드를 위한 슈퍼 노드의 변경 여부를 결정하는 동작; 및상기 인접 노드를 위한 슈퍼 노드의 변경에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하는 동작을 포함하는 컴퓨터 프로그램
|
12 |
12
제 11 항에 있어서, 상기 인접 노드를 위한 슈퍼 노드의 변경 여부를 결정하는 동작은, 코스 클러스터들을 업데이트하는 동작; 상기 변경 노드들의 각각에 대해, 무작위로 선택되는 정해진 개수의 인접 노드들로 테스팅 풀을 구성하는 동작; 상기 테스팅 풀의 일부를 테스팅 노드로 결정하는 동작; 및상기 테스팅 노드에 대한 테스팅을 통해, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작을 포함하는 컴퓨터 프로그램
|
13 |
13
제 12 항에 있어서, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작은,상기 테스팅 노드를 포함하는 코스 클러스터를 확인하는 동작; 상기 테스팅 풀과 상기 코스 클러스터에 공동으로 속하는 노드들로 후보 풀을 구성하는 동작;상기 후보 풀로부터 후보 노드를 선택하는 동작; 상기 테스팅 노드에 대해 상기 후보 노드의 슈퍼 노드로의 이동에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하는 동작; 및상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하는 동작을 포함하는 컴퓨터 프로그램
|
14 |
14
제 12 항에 있어서, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하는 동작은,상기 테스팅 노드에 대해 단독 슈퍼 노드로의 생성에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하는 동작; 및상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하는 동작을 포함하는 컴퓨터 프로그램
|
15 |
15
전자 장치에 있어서, 메모리; 및상기 메모리와 연결되고, 상기 메모리에 저장된 적어도 하나의 명령을 실행하도록 구성된 프로세서를 포함하고, 상기 프로세서는, 대규모 그래프로부터 요약되는 요약 그래프 및 상기 대규모 그래프와 상기 요약 그래프 간 차이를 나타내는 교정 정보를 저장하고, 상기 대규모 그래프에서 변경 엣지를 검출하고, 상기 변경 엣지에 기반하여, 상기 변경 엣지에 의해 연결되는 변경 노드들을 검출하고, 상기 변경 노드들의 각각에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하도록 구성되는 장치
|
16 |
16
제 15 항에 있어서, 상기 요약 그래프는,상기 대규모 그래프로부터 검출되는 복수 개의 노드들과 상기 노드들을 연결하는 엣지들로부터 요약되는 적어도 하나의 슈퍼 노드와 상기 슈퍼 노드를 연결하는 적어도 하나의 슈퍼 엣지로 이루어지고, 상기 변경 엣지는,상기 대규모 그래프에 추가되는 엣지 또는 상기 대규모 그래프로부터 삭제되는 엣지 중 적어도 하나를 포함하는 장치
|
17 |
17
제 16 항에 있어서, 상기 프로세서는, 상기 변경 노드들의 각각의 적어도 하나의 인접 노드를 위한 슈퍼 노드의 변경 여부를 결정하고, 상기 인접 노드를 위한 슈퍼 노드의 변경에 기반하여, 상기 요약 그래프 및 상기 교정 정보를 업데이트하도록 구성되는 장치
|
18 |
18
제 17 항에 있어서, 상기 프로세서는,코스 클러스터들을 업데이트하고, 상기 변경 노드들의 각각에 대해, 무작위로 선택되는 정해진 개수의 인접 노드들로 테스팅 풀을 구성하고, 상기 테스팅 풀의 일부를 테스팅 노드로 결정하고, 상기 테스팅 노드에 대한 테스팅을 통해, 상기 테스팅 노드를 위한 슈퍼 노드를 결정하도록 구성되는 장치
|
19 |
19
제 18 항에 있어서, 상기 프로세서는, 상기 테스팅 노드를 포함하는 코스 클러스터를 확인하고, 상기 테스팅 풀과 상기 코스 클러스터에 공동으로 속하는 노드들로 후보 풀을 구성하고, 상기 후보 풀로부터 후보 노드를 선택하고, 상기 테스팅 노드에 대해 상기 후보 노드의 슈퍼 노드로의 이동에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하고, 상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하도록 구성되는 장치
|
20 |
20
제 18 항에 있어서, 상기 프로세서는, 상기 테스팅 노드에 대해 단독 슈퍼 노드로의 생성에 기반하여, 상기 요약 그래프 및 상기 교정 정보의 업데이트에 따른 크기 변화를 계산하고, 상기 크기 변화가 음이면, 상기 테스팅 노드에 대해 상기 이동된 슈퍼 노드를 유지하고, 그렇지 않으면, 상기 테스팅 노드에 대해 원래의 슈퍼 노드로 복귀하도록 구성되는 장치
|