Patent Document ID: 9749406
Application ID: 14207205

Base Claim:
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.

---

Claim 6:
6. The system as set forth in claim 1 , wherein similarity is defined using a product of a similarity function over edge types.