System and method for discovering ad-hoc communities over large-scale implicit networks by wave relaxation

Patent metadata

Field	Value
Publication number	US-11979309-B2
Application number	US-201514954633-A
Country	US
Kind code	B2
Filing date	Nov 30, 2015
Priority date	Nov 30, 2015
Publication date	May 7, 2024
Grant date	May 7, 2024

Abstract

A method includes computing a diffusion vector starting with a seed, querying nodes for connections, reweighting diffusion vector based on the degrees, sorting nodes based upon magnitude in the reweighted diffusion vector which is obtained through wave relaxation solution of a time-dependent initial value problem, detecting a community through a sweep over the nodes according to their rank, and selecting a prefix that minimizes or maximizes an objective function.

First claim

What is claimed is:

1. A method of discovering communities, comprising:
computing a diffusion vector by a processor including weights that starts with a seed;
querying nodes of networks for connections;
reweighting the diffusion vector;
sorting the nodes based upon at least a magnitude in the reweighted diffusion vector;
detecting a community over the networks in an ad-hoc manner by at least sweeping over the nodes according to their rank by the processor in a computer through wave relaxation,
wherein the detecting the community includes controlling a predetermined condition of the community; and
discovering ad-hoc communities over implicit networks by wave relaxation,
wherein the detecting of the ad-hoc communities includes controlling a predetermined tightness of a local community that is found.

2. The method according to claim 1 , wherein the community is detected using a wave relaxation algorithm, and
the computing of the diffusion vector starts with a seed, and
further comprising selecting a prefix that minimizes or maximizes an objective function; ranking association between web-pages, associates, or social media type applications; and
discovering ad-hoc communities over the networks,
wherein the detecting includes diffusion-based community detection algorithm or a wave relaxation algorithm querying the nodes for connections, and where computation is localized,
wherein a recommender system is added for a set of skills relevant to a predetermined membership,
wherein the detecting the community includes controlling the predetermined condition of the community based on a graph of the network.

3. The method according to claim 1 , further comprising:
ranking association between web-pages, associates, or social media type applications; and
integrating with a recommender system, if several members have an overlapping set of attributes, for a set of skills relevant to a predetermined membership,
wherein an algorithm queries the nodes for connections, and computation is localized, and
wherein the detecting includes diffusion-based community detection algorithm.

4. The method according to claim 1 , further comprising:
integrating with a recommender system, if several members have an overlapping set of attributes, for a set of skills relevant to a predetermined membership, and
discovering ad-hoc communities includes controlling a predetermined tightness of a local community.

5. The method according to claim 1 , wherein the diffusion vector is determined through a predetermined initial value problem,
wherein the diffusion vector is locally determined, and
wherein an algorithm constructs a vector valued function that approximates the diffusion vector.

6. The method according to claim 1 , further comprising: discovering ad-hoc communities over networks;
wherein the detecting of the ad-hoc communities includes controlling a community,
wherein a seed vector initializes a diffusion vector,
wherein the detecting of the community is based on a graph of the networks.

7. A system, comprising:
a server comprising:
a processor; and
a computer readable medium storing a program executed by the processor,

wherein the server computes a diffusion vector including weights that starts with a seed,
wherein the server querying nodes of networks for connections,
wherein the server reweights the diffusion vector,
wherein the server sorts nodes based upon magnitude in the reweighted diffusion vector, and
wherein the server detects, by the processor, a community over the networks in an ad-hoc manner by sweeping over the nodes according to their rank,
wherein the server discovers ad-hoc communities over implicit networks by wave relaxation,
further comprising:
integrating with a recommender system, if several members have an overlapping set of attributes, for a set of skills relevant to a predetermined membership, and
discovering ad-hoc communities includes controlling a predetermined tightness of a local community.

8. The system according to claim 7 , further comprising:
discovering ad-hoc communities over the networks,
wherein the community is detected using a wave relaxation algorithm,
wherein the server computes the diffusion vector starting with a seed, and
wherein the server selects a prefix that minimizes or maximizes an objective function,
wherein the server detects the community includes controlling a predetermined condition of the community based on a graph of the network.

9. The system according to claim 7 , further comprising:
the server ranking association between web-pages, associates, or social media type applications, and
wherein the server detects the community over the networks in the ad-hoc manner by sweeping over the nodes according to their rank by the processor in the server through wave relaxation.

10. The system according to claim 7 , further comprising of integrating with a recommender system, if several members have an overlapping set of attributes, for a set of skills relevant to a predetermined membership.

11. The system according to claim 7 , wherein the diffusion vector is determined by the server through a predetermined initial value problem, and
wherein the diffusion vector is locally determined within the server.

12. The system according to claim 7 , wherein a seed vector initializes a diffusion vector by the server.

13. The system according to claim 7 , wherein the server discovers ad-hoc communities over implicit networks by wave relaxation.

14. The system according to claim 7 , wherein the server comprises a cloud-based implementation.

15. A server, comprising:
a processor; and
a computer readable medium storing a program executed by the processor,

wherein the server computes a diffusion vector including weights that starts with a seed,
wherein the processor querying nodes of networks for connections,
wherein the processor reweights the diffusion vector,
wherein the processor sorts nodes based upon a magnitude in the reweighted diffusion vector,
wherein the processor detects a community over the networks by sweeping over the nodes according to their rank according to the program stored on the computer readable medium,
wherein the server discovers ad-hoc communities over implicit networks by wave relaxation, and
wherein the server comprises a cloud-based implementation, and
wherein the discovering ad-hoc communities includes controlling a predetermined tightness of a local community that is found.

16. The server according to claim 15 , further comprising:
discovering ad-hoc communities over the networks,
wherein the discovering of the ad-hoc communities includes controlling a community,
wherein the community is detected by the processor using a wave relaxation algorithm,
wherein the processor computes the diffusion vector starting with a seed,
wherein the processor selects a prefix that minimizes or maximizes an objective function, and
wherein the processor detects the community includes controlling a predetermined condition of the community based on a graph of the network.

17. The server according to claim 15 , further comprising integrating with a recommender system, when at least one member has an overlapping set of attributes, for a set of skills relevant to a predetermined membership; and
wherein the processor ranks association between web-pages, associates, or social media type applications.

18. The server according to claim 15 , wherein the processor integrates with a recommender system, if several members have an overlapping set of

Assignees

• IBM

Inventors

• Avron Haim
• Horesh Lior
• Horesh Raya
• Tripp Omer

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L67/10 Primary

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title