System and methods for automated community discovery in networks with multiple relational types

Patent metadata

Field	Value
Publication number	US-9749406-B1
Application number	US-201414207205-A
Country	US
Kind code	B1
Filing date	Mar 12, 2014
Priority date	Mar 13, 2013
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

Described is a system for automated community discovery in networks with multiple relational types. The system receives a network as input. The network comprises neighbors, edges connecting the neighbors, and vertices, where edges between two vertices represent a relation. A set of pair-wise similarity comparisons is computed for all pairs of relations. Two relations are considered similar if vertices connected to the two relations share similar relations to the same set of neighbors. A relation dendrogram is created based on the set of pair-wise similarity comparisons. Then, a cut in the relation dendrogram is selected to compute a community solution, resulting in a plurality of relation dendrogram partitions. Each relation dendrogram partition represents a community. A community density criterion is computed based on a density of each community calculated with respect to edge types contained within each community. Finally, a community solution is generated that maximizes the community density criterion.

First claim

What is claimed is:

1. A system for automated community discovery in networks with multiple relational types, the system comprising:
one or more processors and a non-transitory computer-readable medium having executable instructions encoded thereon such that when executed, the one or more processors perform operations of:
receiving as input a network comprising a plurality of neighbors, edges connecting the plurality of neighbors, and vertices, wherein edges between two vertices represent a relation;
computing a set of pair-wise similarity comparisons for all pairs of relations, wherein two relations are similar if vertices connected to the two relations share similar relations to the same set of neighbors,
wherein similarity is defined to be proportional to a percentage of neighbors that are shared in common with respect to the similarity of edge types connecting the neighbors;
creating a relation dendrogram based on the set of pair-wise similarity comparisons;
selecting a cut in the relation dendrogram to compute a community solution, resulting in a plurality of relation dendrogram partitions, each relation dendrogram partition representing a community;
computing a community density criterion based on a density of each community calculated with respect to edge types contained within each community; and
generating a community solution that maximizes the community density criterion,
wherein similarity is defined according to the following similarity function:

sim
⁡

(

r

i
,
k

⁢

r

j
,
k

)

=

f
⁡

(

N
i

,

N
j

)



N
i



2

+



N
j



2

-

f
⁡

(

N
i

,

N
j

)

where r i,k , r j,k represents two relations which share a vertex k and where i≠j, N represents a neighbor, and f(N i , N j ) is defined as:

f
⁡

(

N
i

,

N
j

)

=

∑

m
∈

N
i

⋂

N
j

⁢

⁢

∑

e

i
,
m

∈

E

i
,
m

⁢

⁢

∑

e

j
,
m

∈

E

j
,
m

⁢

⁢

σ
⁡

(

e

i
,
m

,

e

j
,
m

)

,

where σ(e i,m , e j,m ) is a similarity function over the edge types of edge e i,m and edge e j,m , Σ is a summation, and E i,j denotes a set of edge types connecting vertices i and j.

2. The system as set forth in claim 1 , wherein the one or more processors further perform an operation of measuring a total goodness of a community as the sum of the commun

Assignees

• Hrl Lab Llc

Inventors

• Jurgens David A
• Lu Tsai-Ching

Classifications

• H04L67/1061 Primary

  using node-based peer discovery mechanisms (static access to replicated servers H04L67/1006; service discovery H04L67/51) · CPC title

• H04L12/44 Primary

  Star or tree networks · CPC title