특허 효과

최근에 인터넷상에서 몇몇 온라인 데이팅 및 친구 만들기 사이트들이 운용된다. 이러한 서비스들은 일반적으로기능면에서 유사하다. 그들은 사용자들이 다른 사용자들의 프로필들이나 사진들을 통한 검색을 허락할 뿐 아니라, 사용자들이 프로필이나 사진을 개시하는 것을 허락한다. 사용자들이 필명으로 식별되므로, 사용자들 사이의 통신은 익명성이 보장된다.

처음에, 이러한 사이트들은 사용자들을 연결(match)시키기 위해 초보적인 기술들을 수행하였다. 이러한 기술들은 결국은 단지 나이, 성별, 위치, 그리고 신체적 특징과 같은 판별 기준에 기초하여 사용자 프로필을 검색 하는것이다. 최근 들어, 이러한 사이트들은 사용자들에 대해 보다 나은 연결을 찾기 위한 노력으로 보다 정교한 프로세스를 실행해 왔다. 이러한 프로세스들은 특별히 설계된 테스트나 질문서에 기초하여 개인의 성격을 평가하고, 성격이 일치되는 사용자들을 찾으려고 시도한다.

본 발명은 사회망에서 회원인 두 개인들의 일치성을 개인들에 의해 표명된 관심들의 일치성에 근거하여 구한다.

본 발명은 관심들의 일치성을 정량화하는 방법, 개인들에 의해 표명된 관심들의 일치성에 따라서 두 개인들의일치성을 점수화하는 방법 및 일치성 점수를 포함하는 일치성 결과를 제시하는 방법을 제공한다.

관심들의 일치성을 정량화하는 방법은, 각 관심에 관련된 추정 확률(이하, "관심 확률")과 관심들의 쌍 각각에관련되는 추정 확률(이하, "결합 확률")을 계산하는 단계, 및 추정 확률들에 기초하여 각 쌍의 관심들 사이의 관심 일치성 점수를 할당하는 단계를 포함한다.

특정 관심에 대한 추정 관심 확률은 사회망의 회원이 상기 관심을 그의 또는 그녀의 관심으로서 표명할 확률을 의미한다.

관심들의 특정 쌍에 대한 추정 결합 확률은 사회망의 회원이 그 쌍의 두 관심을 그의 또는 그녀의 관심들로서 표명할 확률을 의미한다.

본 발명의 일 실시예에 따라서, 각 쌍의 관심들 사이의 관심 일치성 점수는 그 쌍에 대한 추정 결합 확률과 그쌍의 제 1 관심과 제 2 관심에 대한 추정 관심 확률들의 함수로서 계산된다.

관심들의 일치성에 따라서 일치성을 점수화하는 방법은, 사회망에서 회원들의 표명된 관심들에 기초하여 관심 일치성 점수들을 준비하는 단계, 사회망의 제 1 회원과 사회망의 제 2 회원 간의 일치성 점수를, 제 1 회원의표명된 관심들, 제 2 회원의 표명된 관심들, 제 1 회원의 표명된 관심들과 제 2 회원의 표명된 관심들 사이의관심 일치성 점수들에 기초하여 계산하는 단계를 포함한다.

임의의 두 표명된 관심들에 대한 관심 일치성 점수는 두 표명된 관심들 사이의 일치도(degree of compatibility)를 나타낸다.

일치성 점수들을 포함하는 일치성 결과들을, 예를 들어, 사회망의 개인 회원에게 제시하는 방법은, 사회망에서 개인들의 표명된 관심들에 기초하여 관심 일치성 점수들을 준비하는 단계, 제 1 개인으로부터 미리 결정된 분리도(degree of separation) 내에 있는 개인들의 집합을 선택하는 단계, 및 상기 집합의 각 개인들과 제 1 개인사이의 일치성 점수를 계산하는 단계를 구비한다. 미리 결정된 분리도가 "1"로 설정되면, 이것은 단지 제 1 개인의 직접 친구들의 일치성 점수만이 제시됨을 의미한다. 일치성 점수들을 포함하는 일치성 결과들이 웹 페이지로서 제시되고, 웹 페이지가 디스플레이를 위해 전송되기 전에, 일치성 결과들은 일치성 점수들의 순서에 따라 정렬된다.

일치성 점수들을 제공하고 이 일치성 점수들을 관심 프로필들에 링크시키는 것에 의해서, 본 발명은사람들이 관심들을 입력하는 것을 장려함으로써, 사이트는 동일하거나 유사한 관심들을 공유하는 다른 사람들을 찾을 수 있다.

본 발명의 상술한 특징이 상세히 이해될 수 있도록, 실시예를 참조하여 본 발명을 자세히 기술하고, 일부 특징을 첨부 도면에 나타낸다. 그러나 첨부 도면은 본 발명의 전형적인 실시예를 나타낼 뿐이고, 다른 실시예들을포함할 수 있는 본 발명의 범위를 제한하는 것은 아니다.

본 발명이 제공하는, 사회망의 개인들이 표명한 관심들의 일치성을 정량화하는 방법, 개인들에 의해 표명된 관심들의 일치성에 따라서 두 개인들의 일치성을 점수화하는 방법 및 일치성 점수를 포함하는 일치성 결과를 제시하는 방법은 온라인 데이팅 및 친구 만들기 사이트들에 이용될 수 있다.

특허 기술 설명

본 발명은 일반적으로 사회망 데이터의 처리에 관한 것이고, 더욱 상세하게는 온라인 사회망에서 회원들 사이의
일치성을 점수화하는 방법에 관한 것이다.

도1) 개인(ME)을 중앙에 둔 사회망의 그래프 표현

이 사회망에 다른 회원들 A-U가 포함되고, ME에 대한 다른 회원들의 위치는 ME와 각 회원 사이의 분리도로 불린다.

A,B 및 C를 포함하는 ME의 친구는 ME로부터1 분리도(1 d/s) 만큼 분리되어 있다.

ME의 친구의 친구는 ME로부터 2 d/s 만큼 분리되어 있다. 도시된 바와 같이, D,E,F,G 및 H는 ME로부터 각각 2 d/s 만큼 분리되어 있다.

ME의 친구의 친구의 친구는 ME로부터 3 d/s만큼분리되어 있다.

도 1은 ME로부터 3 분리도 이상 떨어진 모든 노드들을 ALL 범주에 속하는 것으로 표시한다.

사회망에서 분리도는 개인에 대하여 정의된다.

예를 들어, ME의 사회망에서 H와 ME는 2 d/s 만큼 분리되어 있는반면, G의 사회망에서 H와 G는 단지 1 d/s 만큼 분리되어 있다. 따라서 각 개인은 그들 자신의 제 1 단계 관계집합(set of first degree relationship), 제 2 단계 관계 집합, 제 3 단계 관계 집합을 가질 수 있다.

본 기술 분야의 당업자들이 이해하는 바와 같이, 개인의 사회망은 N 분리도의 노드들을 포함하도록 확장될 수도있다.

그러나 분리도가 3 이상으로 증가하면, 일반적으로 노드들의 수가 폭발적인 비율로 빠르게 증가하고, ALL집합과 흡사해지기 시작한다.

도2) 온라인 사회망을 생성하고 관리하는 시스템을 도시하는 블럭도

도시된 바와 같이, 도 2에 도시된시스템(250)은 응용 서버(application server, 251)와 하나 이상의 그래프 서버(252)를 포함한다.

시스템(250)은 예를 들어 인터넷과 같은 네트워크(260)에 연결되고, 이 네트워크를 통해, 270으로 일괄하여 표시된 복수의 컴퓨터에 의해 접속될 수 있다.

응용 서버(250)는 회원 데이터베이스(254), 관계 데이터베이스(255), 및 검색 데이터베이스(256)를 관리한다.

회원 데이터베이스(254)는 시스템(250)에 의해 관리되는 온라인 사회망내 각회원들의 프로필 정보를 포함한다.

프로필 정보는 유일한 회원 식별자, 이름, 나이, 성별, 위치, 고향, 이미지파일에 대한 참조들, 관심들의 리스트, 속성 등을 포함할 수 있다. 관계 데이터베이스(255)는 회원들 사이의 제1 단계 관계들을 정의하는 정보를 저장한다.

이에 더하여, 회원 데이터베이스(254)의 항목들은 검색을 위해 색인되고 최적화되며, 검색 데이터베이스(256)에 저장된다. 회원 데이터베이스(254), 관계 데이터베이스(255), 그리고 검색 데이터베이스(256)는 컴퓨터들(270)에 의해 행해지는 신규 회원 정보의 입력과 기존 회원 정보의 편집을 반영하기 위해 갱신된다.

응용 서버(251)는 또한 원격 컴퓨터들(270)로부터 수신한 정보 교환 요청을 관리한다. 그래프 서버(252)는 응용서버(251)로부터 질문(query)을 수신하고, 질문을 처리한 후 질문 결과를 응용 서버(251)로 되돌려준다.

그래프서버(252)는 회원 데이터베이스의 모든 회원들에 대한 사회망의 표시를 관리한다.

그래프 서버(252)는 사회망에서 모든 제 1 단계 관계를 나타내는 인접 리스트를 저장하는 랜덤 액세스 메모리(RAM)와 같은 전용 메모리 디바이스(253)를 갖는다. 그래프 서버(252)는 응용 서버(251)로부터의 요청에 응답하여, 온라인 사회망에서 회원들사이의 관계 및 분리도를 확인한다.

도3) 회원 데이터베이스(254)

회원 데이터베이스(254)를 더욱 자세하게 도시하고, 저장된 관심 데이터가 먼저 정규화된 관심들의 집합(310)으로 변환된 후에, 관심 일치성 점수들의 매트릭스(320)로 변환됨을 나타낸다.

정규화된 관심들로의 변환,및 그 후 관심 일치성 점수들로의 변환은 응용 서버(251)의 프로세싱 유닛에 의해 실행된다.

관심 정규화 프로세스는 본질적으로 관심 분류 프로세스이다. 관심 분류 프로세스는 다른 방식으로 표명된 동일한 관심이 동일한 관심에 속하게 분류되도록 실행된다.

예를 들어, 독서(reading)로 표명된 관심은 도서들(books)로 표명된 관심과 동일한 정규화된 관심에 속하도록 분류될 수 있다. 도 3에 도시된 정규화된 관심들의집합(310)에서, 리스트로 정규화된 관심들이 보여진다. 다른 실시예에서 정규화된 관심들은 계층 트리로 배열될수 있다.

더욱이, 본 발명은 시스템 운용자에 의해 미리 결정된 하나 이상의 관심을 회원들이 선택하여 입력하는 시스템에 적용될 수도 있다. 이와 같은 경우, 정규화 과정은 실행되지 않고 미리 결정된 관심들의 집합이 정규화된 관심들의 집합(310)으로 사용된다.

관심 일치성 점수의 매트릭스(320)는 정규화된 관심들(관심 1, 관심2, …, 관심 N)의 각 쌍이 얼마나 일치하는지를 나타내는 수치적 점수를 제공한다.

매트릭스(320)에서 대각선 외의 셀 각각은, 그 셀의 행과 열에 연관된두 개의 관심들의 일치성을 나타내는 수치적 점수 입력을 갖는다. 매트릭스(320)의 대각선 셀 각각은 그 셀의행과 열에 연관된 관심들의 희박성(rarity) 측정치인 수치적 점수 입력을 갖는다.

희박한 관심은 높은 점수를 가지고, 보편적으로 발생하는 관심은 낮은 점수를 갖는다. 여기에 도시된 본 발명의 실시예에서, 관심 일치성점수들은 정규화된 회원들의 표명된 관심들에 기초하여 자동으로 축적(compile)된다.

관심 일치성 점수는 수동으로 생성되거나, 자동 및 수동 프로세스의 조합을 사용하여 생성될 수도 있다. 더 나아가, 자동으로 축적된 임의의 관심 일치성 점수는 수동으로 조정될 수도 있다.

도4) 매트릭스(320)를 생성하는데 관계된 프로세스 과정을 도시한 순서도

410 단계에서, 회원 데이터베이스(254)에 저장된 모든 표명된 관심들은 정규화된 관심들(관심1, 관심2, …, 관심N)의 집합(310)으로 정규화된다.

410 단계에서는 클러스터링으로 알려진 표준 데이터 마이닝 방법론을 사용할 수 있다. 각 정규화된 관심(I)에 대한 확률(P(I))이 계산된다(단계 411). P(I)는 회원이 정규화된 관심(I)에 해당하는 관심을 표명할 확률을 의미하고, 회원 데이터베이스(254)에 저장된 표명된 관심들을 사용하여 [수학식 1]에 따라 계산된다.

[수학식 1]

P(I)= (회원 데이터베이스(254)에서, 정규화된 관심(I)에 해당하는 관심이 표명된 횟수)/(회원 데이터베이스(254)내 표명된 관심의 총 수).

정규화된 관심들(I1과 I2)의 각 쌍에 대한 확률 P(I1, I2)이 계산된다(단계 412). P(I1, I2)는 회원이 정규화된관심들(I1과 I2)에 해당하는 관심들을 표명할 확률을 의미하고, 회원 데이터베이스(254)에 저장된 표명된 관심들을 사용하여 [수학식 2]에 따라 계산된다.

[수학식 2]

P(I1, I2) = (회원 데이터베이스(254)에서, 두 정규화된 관심들(I1, I2)에 해당하는 관심들을 표명하는 회원들의 수)/(회원 데이터베이스(254)내 표명된 관심들의 총 수).

1=I2 인 경우, P(I1, I2)는 P(I1) 또는 P(I2)로 설정된다. 413 단계에서 각 쌍의 정규화된 관심들 사이의 관심일치성 점수 S(Ii, Ij)는 [수학식 3]에 따라 계산된다.

[수학식 3]

S(Ii, Ij) = log[P(Ii,Ij)/(P(Ii)*P(Ij))].

상기 수학식은 [(P(Ii)*P(Ij)]로 나누기 때문에, 희박한 관심들의 공통성(commonality)은 더 대중적인 관심들의공통성보다 더 높이 평가된다.

도5) 두 회원(예를 들어, 제 1 회원과 제 2 회원)간의 일치성 점수를 계산하는 응용 서버(251)의 프로세서에의해 실행되는 프로세스 과정을 도시한 순서도

510 단계에서 제 1 회원의 표명된 관심들은 정규화된 관심들의 제 1 집합{I1, I2, …, Im}으로 정규화된다. 여기서, m은 제 1 집합에서 정규화된 관심들의 개수를 의미한다.

511 단계에서 제 2 회원의 표명된 관심들은 정규화된 관심의 제 2 집합 {Ji, J2, …, Jn}으로 정규화된다.

여기서, n은 제 2 집합에서 정규화된 관심들의 개수를 의미한다. 512 단계에서 제 1 집합과 제 2 집합에서 정규화된 관심들의 모든 쌍에 대한 관심 일치성 점수들이 매트릭스(320)로부터 계산된다. 예를 들어, 제 1 집합이{관심_1, 관심_2}이고 제 2 집합이 {관심_2, 관심_3}이면, 아래의 관심 일치성 점수들은 매트릭스(320)로부터 해진다.

일치성(관심_1, 관심_2);

일치성(관심_1, 관심_3);

일치성(관심_2, 관심_2); 및

일치성(관심_2, 관심_3).

513 단계에서, 단계 512에서 결정된 관심 일치성 점수들은 합산되고, 이 합은 제 1 회원과 제 2 회원 사이의 일치성 점수를 나타낸다.

도 6) 사회망의 회원에 의해 명시(Specified)된 조건의 집합을 만족하는 회원들의 일치성 점수를 제시하는,응용 서버(251)의 프로세서에 의해 수행되는 처리 과정을 도시한 순서도이다.

610 단계에서, 명시된 조건을 만족하는 사회망의 회원들이 선택된다.

도7) 집합을 명시하기 위한 그래픽 사용자 인터페이스(GUI)의 실시예

GUI(700)는 회원에 의해 명시될 수 있는 조건을 보여준다. 조건에는 나이, 성별(남자,여자, 남자&여자), 위치, 검색 목적, 관계 상태, 및 선택된 카테고리(예를 들어, 고향, 회사들, 학교들, 당파,관심들, 좋아하는 영화들, 좋아하는 책들, 좋아하는 음악, 그리고 좋아하는 TV 프로그램들)의 검색어가 포함된다.

GUI는 분리도(d/s)에 대한 설정을 제공한다. 상기 분리도는 1 분리도 이내의 회원들, 2 분리도 이내의 회원들, 3 분리도 이내의 회원들, 또는 모든 회원으로 설정할 수 있다.

조건을 명시한 후에, 회원이 검색 버튼(710)을 클릭하면, 이에 응답하여 응용 서버(251)는 명시된 조건을 만족시키는 회원들에 대한 검색을 수행한다.

611 단계에서, 조건을 명시한 회원과 명시된 조건 검색을 만족시키는 사회망의 각 회원 사이의 일치성 점수가계산된다.

612 단계에서, 명시된 검색 조건을 만족시키는 사회망의 회원들은 그들의 일치성 점수들에 따라 정렬된다.

613 단계에서, 명시된 검색 조건을 만족하는 사회망의 회원들과 관련된 이미지, 미니-프로필들, 그리고하이퍼링크들을 포함하는 웹 페이지가 디스플레이를 위해 회원들에게 전송된다.

613 단계에서 전송된 웹 페이지는 회원들과 관련되는 이미지, 미니-프로필들, 및 하이퍼링크들이 그들의 일치성 점수(최고부터 최저)에 따라표시되도록 서식화(formatted)된다. 도 8은 검색 결과 페이지(800)의 예를 보여준다.

두 회원 사이의 일치성 점수는 두 회원에 대해 저장된 관계 정보를 기반으로 조정될 수 있다.

제 1 실시예에서,두 회원 사이의 일치성 점수는 그 회원들이 갖는 첫 번째 단계부터 N 번째 단계의 공통 친구들의 수에 기초하여증가된다. N은 일반적으로 2 또는 3으로 설정되지만, 임의의 양수가 될 수 있다.

일치성 점수는 회원들이 갖는첫 번째 단계부터 N 번째 단계의 공통 친구들의 수에 비례하여 증가할 수도 있다. 증가에 있어서 첫 번째 단계친구들을 기반으로 하는 증가는 두 번째 단계 친구들을 기반으로 하는 증가보다 높은 가중치가 주어지고,

두 번째 단계 친구들을 기반으로 하는 증가는 세 번째 단계 친구들을 기반으로 하는 증가보다 높은 가중치가 주어지는 등등으로 된다.

다른 실시예에서, 사회망의 제 1 회원과 사회망의 제 2 회원 사이의 일치성 점수는, 제 1 회원의 사회망에서 제1 회원의 표명된 관심이 갖는 공통성(commonality)과 제 2 회원의 사회망에서 제 2 회원의 표명된 관심이 갖는공통성에 기초하여 조정된다.

도 9) 두 회원(예를 들어, 제 1 회원과 제 2 회원)의 일치성 점수를 제 1 회원의 회망에서 제 1 회원의 표명된 관심이 갖는 공통성과 제 2 회원의 사회망에서 제 2 회원의 표명된 관심이 갖는공통성에 기초하여 조정하여 계산하는, 응용 서버(251)의 프로세스에 의해 실행되는 처리 과정을 도시한 흐름도이다. 


  

910 단계에서, 제 1 회원의 표명된 관심들은 정규화된 관심들의 제 1 집합 {I1, I2, …, Im}으로 정규화된다.

여기서, m은 제 1 집합에서 정규화된 관심들의 개수를 의미한다. 911 단계에서, 제 2 회원의 표명된 관심들은정규화된 관심들의 제 2 집합 {J1, J2, …, Jn}으로 정규화된다. 912 단계에서, 제 1 집합과 제 2 집합의 정규화된 관심들의 모든 쌍에 대한 관심 일치성 점수는 매트릭스(320)로부터 결정된다.

예를 들면, 제 1 집합이 {관심_1, 관심_2}이고 제 2 집합이 {관심_2, 관심_3}이면, 아래의 관심 일치성 점수는 매트리스(320)로부터 구해진다.

일치성(관심_1, 관심_2);

일치성(관심_1, 관심 3);

일치성(관심_2, 관심_2); 및

일치성(관심_2, 관심_3).

913 단계에서, 912 단계에서 결정된 각 관심 일치성 점수는, 제 1 회원의 사회망에서 제 1 회원의 표명된 관심이 갖는 공통성과 제 2 회원의 사회망에서 제 2 회원의 표명된 관심이 갖는 공통성에 근거하여 조정된다.

예를들어, 912 단계에서 결정된 관심 일치성 점수에 대하여 조정 k12, k13, k22, k23 들은 아래와 같이 이루어진다.

k12 * 일치성(관심_1, 관심_2);

k13 * 일치성(관심_1, 관심 3);

k22 * 일치성(관심_2, 관심_2); 및

k23 * 일치성(관심_2, 관심_3).

조정 kij는, 관심_i에 해당하는 관심을 표명한 제 1 회원의 첫 번째 단계부터 N번째 단계 친구들의 수 및 관심_j에 해당하는 관심을 표명한 제 2 회원의 첫 번째 단계부터 N 번째 단계 친구들의 수로 이루어진 함수이다.

N은 대표적으로 3 또는 4로 설정되지만, 임의의 양수로 설정될 수도 있다. 조정 kij의 속성은 다음과 같다.

1.kij≥1;

2.kij = kji

3. kij는 관심_i에 해당하는 관심을 표명한 제 1 회원의 친구 수에 비례하여 증가하며, 증가의 양은 가까운 단계 친구들에게 높은 가중치가 부여된다.

4. kij는 관심_j에 해당하는 관심을 표명한 제 2 회원의 친구 수에 비례하여 증가하며, 증가의 양은 가까운 단계 친구들에 대해 높은 가중치가 부여된다.

914 단계에서, 913 단계에서 결정되어 조정된 관심 일치성 점수가 합산되고, 그 합은 제 1 회원과 제 2 회원 사이의 일치성 점수를 나타낸다.

위에서 본 발명에 따른 특별한 실시예가 도시되고 설명되었다 하더라도, 당업자는 본 발명이 첨부된 청구 범위내에서 다양한 형태와 실시예를 취할 수 있음을 안다.

발명자: 주 지아오 밍, 런트 크리스토퍼

대리인: 특허법인태평양