topic Re: How to find link between nodes in SAS Programming

How to find link between nodes

gyambqt — Fri, 17 Mar 2017 00:07:28 GMT

Hi Experts,

I want to find all the links that are connected to the address_ID I specified directly or indirectly (or any other nodeID, like email_ID, IP_ID etc.) and return only application_ID. for example:

Application_ID Email_ID IP_ID Address_ID phone_ID

1 email1 ip1 address1 phone1

2 email2 ip2 address1 phone2

3 email3 ip2 address2 phone5

4 email5 ip1 address3 phone13

5 email1 ip13 address13 phone13

if I specify parameter address_id=address1

then the program should able to return all 5 applications because

address1 is connected to ip1 and ip2 from application_id 1 and application_id 2 so both application should be returned in the final output

address1 is connected to ip1 which also connected to application_id 4 so appliation_id 4 should be returned in the final output

address1 is connected to ip2 which is connected to application_id 3 so applicaiton_id 3 should be returned in the final output

address1 is connected to email1 which is conneted to application_id 5 so application_id 5 should be returned in the final output

I have used pro sql join to handle this problem but it seems to be inefficient as I need to specify number of time the iteration should run.

I want to achieve the outcome using hash table if possible!

I hope I made it clear.

Thanks

Re: How to find link between nodes

PGStats — Fri, 17 Mar 2017 03:02:42 GMT

Build the set of all connections, then use the subgraphs macro described here. It is a hash solution to this problem.

Re: How to find link between nodes

Ksharp — Fri, 17 Mar 2017 03:31:48 GMT

Since those four variables are independent respectively,
it is easy for SQL.



data have;
input Application_ID   (Email_ID  IP_ID Address_ID phone_ID) ( :$20.);
cards;
1                            email1    ip1       address1     phone1    
2                            email2    ip2        address1    phone2
3                            email3   ip2         address2    phone5
4                            email5    ip1         address3     phone13
5                            email1  ip13       address13  phone13
;
run;

%let add=address1;

proc sql;


select application_id
 from have
  where email_id in
(select email_id from have where address_id="&add")
  
union

select application_id
 from have
  where ip_id in
(select ip_id from have where address_id="&add")

union

select application_id
 from have
  where phone_id in
(select phone_id from have where address_id="&add")

 ;
 quit;

Re: How to find link between nodes

gyambqt — Fri, 17 Mar 2017 04:14:23 GMT

Hi Ksharp,

Thanks for your reply but I think your code only return part of the node that application linked to, it can go further than that.

like the following example:

Application_ID Email_ID IP_ID Address_ID phone_ID

1 email1 ip1 address1 phone1

2 email2 ip1 address2 phone2

3 email2 ip2 address3 phone3

you code only return application_id 1 and application_id 2

but if you look at the dataset address1 from application_id 1 is linked to application_id 2 via ip1 and application_id 2 is linked to application_id 3 via email2 so application_id 1 is linked to application_id 3 indirectly

Re: How to find link between nodes

gyambqt — Fri, 17 Mar 2017 04:35:27 GMT

Thanks for your reply. but your program is finding the link between node which is not the interests of mine.
I am seeking for the application_id that linked to address_id (I specified) either directly or indirectly.

Re: How to find link between nodes

PGStats — Fri, 17 Mar 2017 04:40:19 GMT

Replace <= by < if you don't want clusters with a single ID

data have;
length Application_ID 8 Email_ID IP_ID Address_ID phone_ID $12;
input Application_ID   Email_ID  IP_ID Address_ID phone_ID;
datalines;
1                            email1    ip1       address1     phone1    
2                            email2    ip2        address1    phone2
3                            email3   ip2         address2    phone5
4                            email5    ip1         address3     phone13
5                            email1  ip13       address13  phone13
6                            email9  ip19       address19  phone19
;

proc sql;
create table arcs as
select 
    a.application_ID as from,
    b.application_ID as to
from 
    have as a inner join
    have as b
    on 
        a.Email_ID = b.Email_ID or
        a.IP_ID = b.IP_ID or
        a.Address_ID = b.Address_ID or 
        a.phone_ID = b.phone_ID
where a.application_ID <= b.application_ID;
quit;

%include "&sasforum\subgraphsmacro.sas";

%subgraphs(arcs);

proc print data=clusters; run;

Re: How to find link between nodes

gyambqt — Fri, 17 Mar 2017 05:08:15 GMT

Hi PG,

I think your program only find direct relationship between two applications for a specified address_id. but it failed to find the indirect relationship like the following data.

1 email1 ip1 address1 phone1

2 email2 ip1 address2 phone2

3 email2 ip2 address3 phone3

1 is having relationship with 3 if address1

another question is in the subgraph macro, it has a macro parameter&colon and it is not defined anywhere.

how do I find this value.

thanks

Re: How to find link between nodes

Ksharp — Fri, 17 Mar 2017 10:31:26 GMT

OK. I see what is different now.
Try this one.





data x;
input Application_ID   (Email_ID  IP_ID Address_ID phone_ID) ( :$20.);
cards;
1                            email1    ip1       address1     phone1    
2                            email2    ip2        address1    phone2
3                            email3   ip2         address2    phone5
4                            email5    ip1         address3     phone13
5                            email1  ip13       address13  phone13
11 email21 ip21 address21 phone21
12 email22 ip21 address22 phone22
13 email22 ip22 address23 phone23
;
run;

data have;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 length from to $ 100;
 do i=1 to dim(x)-1;
  from=x{i};
  do j=i+1 to dim(x);
   to=x{j};output;
  end;
 end;
 keep from to;
run;



data full;
  set have end=last;
  if _n_ eq 1 then do;
   declare hash h();
    h.definekey('node');
     h.definedata('node');
     h.definedone();
  end;
  output;
  node=from; h.replace();
  from=to; to=node;
  output;
  node=from; h.replace();
  if last then h.output(dataset:'node');
  drop node;
run;


data want(keep=node household);
declare hash ha(ordered:'a');
declare hiter hi('ha');
ha.definekey('count');
ha.definedata('last');
ha.definedone();
declare hash _ha(hashexp: 20);
_ha.definekey('key');
_ha.definedone();

if 0 then set full;
declare hash from_to(dataset:'full(where=(from is not missing and to is not missing))',hashexp:20,multidata:'y');
 from_to.definekey('from');
 from_to.definedata('to');
 from_to.definedone();

if 0 then set node;
declare hash no(dataset:'node');
declare hiter hi_no('no');
 no.definekey('node');
 no.definedata('node');
 no.definedone();
 

do while(hi_no.next()=0);
 household+1; output;
 count=1;
 key=node;_ha.add();
 last=node;ha.add();
 rc=hi.first();
 do while(rc=0);
   from=last;rx=from_to.find();
   do while(rx=0);
     key=to;ry=_ha.check();
      if ry ne 0 then do;
       node=to;output;rr=no.remove(key:node);
       key=to;_ha.add();
       count+1;
       last=to;ha.add();
      end;
      rx=from_to.find_next();
   end;
   rc=hi.next();
end;
ha.clear();_ha.clear();
end;
stop;
run;

data final_want;
if _n_=1 then do;
 if 0 then set want;
 declare hash h(dataset:'want');
 h.definekey('node');
 h.definedata('household');
 h.definedone();
end;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 do i=1 to dim(x);
  node=x{i};call missing(household);
  if h.find()=0 then leave;
 end;
 drop i node;
run;
proc print noobs;run;

Re: How to find link between nodes

Ksharp — Fri, 17 Mar 2017 10:37:55 GMT

The last data step could be as simple as the following.




data final_want;
if _n_=1 then do;
 if 0 then set want;
 declare hash h(dataset:'want');
 h.definekey('node');
 h.definedata('household');
 h.definedone();
end;
 set x;
  node=email_id;
  h.find();
 drop  node;
run;
proc print noobs;run;

Re: How to find link between nodes

PGStats — Fri, 17 Mar 2017 17:21:23 GMT

The procedure I gave you does find the correct answer. Unfortunately the forum parser garbled my macro code. Please try again with the attached version.

Re: How to find link between nodes

gyambqt — Mon, 20 Mar 2017 03:40:32 GMT

Thanks for your reply!

your code is very nice! but to further extend a bit, if the data contain missing values like one or all the columns are blank for some applicaitons, how do you handle this problem?

I modified your code a little like below:

data have;

set n;

array x{*} $ Customer_Contact_Number name_dob_cluster1 driver_cluster1 address_75_cluster1;

if driver_cluster1='1' then

driver_cluster1='';

length from to $ 100;

do i=1 to dim(x)-1;

from=x{i};

do j=i+1 to dim(x);

to=x{j};

if from^='' or to^='' then

output;

end;

keep from to;

run;

data have1;

set have;

if from='' then

do;

from1+1;

from=cats('a',from1);

end;

if to='' then

do;

to1+1;

to=cats('b',to1);

end;

run;

so if all of the columns are blank then it should be removed. if one or some of the columns are blank then the blank columns will be assigned a ID like a1, a2 a3 (all the blank column must have a distinct id)

what do you think?

Re: How to find link between nodes

Ksharp — Mon, 20 Mar 2017 05:38:57 GMT

You are on the right way.


data have;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 length from to $ 100;
 do i=1 to dim(x)-1;
  from=x{i};
  do j=i+1 to dim(x);
   to=x{j};

   if not missing(x{i}) and not missing(x{j}) then output;
  
  end;
 end;
 keep from to;
run;



"if one or some of the columns are blank then the blank columns will be assigned a ID like a1, a2 a3 "
I don't understand what you mean. Post an example to describe your question.

Re: How to find link between nodes

gyambqt — Mon, 20 Mar 2017 05:59:45 GMT

I realised using the following statment won't be able to find the correct result because It will ignore both from and to value if one of them is missing.

for example:

from to

1 missing

then that record will be ignored. However it should be included as from=1 might connect to some applications

 if not missing(x{i}) and not missing(x{j}) then output;

Also I think something need to be done at X table by giving a distinct number to all the missing value (so in other words, treat the missing value as distinct ID) so as to get the application number at the last step.

anything wrong please let me know thank!

Re: How to find link between nodes

Ksharp — Mon, 20 Mar 2017 06:15:43 GMT

OK. I know what you mean now.

The best way is filling these missing value as unique value just as you said before.

The following code could give you what you want.

CODE NOT TESTED.

data have;

set have;

array x{*} $ _character_;

do i=1 to dim(x);

if missing(x{i}) then do; n+1; x{i}=cats('a',n);end;

end;

run;

And make sure your character variable's length is big enough to hold 'a9999999' .

Re: How to find link between nodes

gyambqt — Mon, 20 Mar 2017 06:37:23 GMT

cool, I have done things similar but takes ages to run for like 1.3 miliions applications. Maybe I need to find a way to make it more efficent processing. thanks a lot!!!!!

Re: How to find link between nodes

Ksharp — Mon, 20 Mar 2017 10:07:21 GMT

Actually you do not have to transform all the missing into axxxxx .

The only problem exist in this scenario is there is only one non-missing value in obs.like:

id address phone email ..........

1 xx .......rest are all missing .

So you can reduce the number of node like:

data have;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 length from to $ 100;

if cmiss(of x{*})=dim(x) then delete;
 else if cmiss(of x{*})=1 then do;
     from=coalescec(of x{*});to=uuidgen(0);output; end;
 end;
  else do;

          do i=1 to dim(x)-1;
           from=x{i};
            do j=i+1 to dim(x);
             to=x{j};
             if not missing(from) and not missing(to) then output;
             end;
          end;

       end;


 keep from to;
run;

Re: How to find link between nodes

Ksharp — Mon, 20 Mar 2017 11:53:43 GMT

In the last data step, you could add one more option in hash table to fast it.

declare hash h(dataset:'want', hashexp: 20);

Re: How to find link between nodes

Ksharp — Fri, 31 Mar 2017 15:16:28 GMT

Final version code.



data x;
input Application_ID   (Email_ID  IP_ID Address_ID phone_ID) ( :$20.);
cards;
1                            email1    ip1       address1     phone1    
2                            email2    ip2        address1    phone2
3                            email3   ip2         address2    phone5
4                            email5    ip1         address3     phone13
5                            email1  ip13       address13  phone13
11 email21 ip21 address21 phone21
12 email22 ip21 address22 phone22
13 email22 ip22 address23 phone23
;
run;

data have;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 length from to $ 100;

if cmiss(of x{*})=dim(x) then delete;
 else if cmiss(of x{*})=1 then do;
     from=coalescec(of x{*});to=uuidgen(0);output; 
 end;
  else do;

          do i=1 to dim(x)-1;
           from=x{i};
            do j=i+1 to dim(x);
             to=x{j};
             if not missing(from) and not missing(to) then output;
             end;
          end;

       end;


 keep from to;
run;




data full;
  set have end=last;
  if _n_ eq 1 then do;
   declare hash h();
    h.definekey('node');
     h.definedata('node');
     h.definedone();
  end;
  output;
  node=from; h.replace();
  from=to; to=node;
  output;
  node=from; h.replace();
  if last then h.output(dataset:'node');
  drop node;
run;


data want(keep=node household);
declare hash ha(ordered:'a');
declare hiter hi('ha');
ha.definekey('count');
ha.definedata('last');
ha.definedone();
declare hash _ha(hashexp: 20);
_ha.definekey('key');
_ha.definedone();

if 0 then set full;
declare hash from_to(dataset:'full(where=(from is not missing and to is not missing))',hashexp:20,multidata:'y');
 from_to.definekey('from');
 from_to.definedata('to');
 from_to.definedone();

if 0 then set node;
declare hash no(dataset:'node');
declare hiter hi_no('no');
 no.definekey('node');
 no.definedata('node');
 no.definedone();
 

do while(hi_no.next()=0);
 household+1; output;
 count=1;
 key=node;_ha.add();
 last=node;ha.add();
 rc=hi.first();
 do while(rc=0);
   from=last;rx=from_to.find();
   do while(rx=0);
     key=to;ry=_ha.check();
      if ry ne 0 then do;
       node=to;output;rr=no.remove(key:node);
       key=to;_ha.add();
       count+1;
       last=to;ha.add();
      end;
      rx=from_to.find_next();
   end;
   rc=hi.next();
end;
ha.clear();_ha.clear();
end;
stop;
run;

data final_want;
if _n_=1 then do;
 if 0 then set want;
 declare hash h(dataset:'want');
 h.definekey('node');
 h.definedata('household');
 h.definedone();
end;
 set x;
 array x{*} $ Email_ID  IP_ID Address_ID phone_ID;
 do i=1 to dim(x);
  node=x{i};call missing(household);
  if h.find()=0 then leave;
 end;
 drop i node;
run;
proc print noobs;run;

Re: How to find link between nodes

rogerjdeangelis — Fri, 31 Mar 2017 18:26:24 GMT

SAS/WPS/R: How to find links between nodes

link to this message
https://goo.gl/KgN8Xw
https://communities.sas.com/t5/General-SAS-Programming/How-to-find-link-between-nodes/td-p/341819

HAVE
====

Up to 40 obs SD1.HAVE total obs=8

Obs                    STR

 1     za1 > email1 > ip1 > address1 > phone1       >> first cluster
 2     za2 > email2 > ip2 > address1 > phone2
 3     za3 > email3 > ip2 > address2 > phone5
 4     za4 > email5 > ip1 > address3 > phone13
 5     za5 > email1 > ip13 > address13 > phone13

 6     za11 > email21 > ip21 > address21 > phone21  >> second cluster
 7     za12 > email22 > ip21 > address22 > phone22
 8     za13 > email22 > ip22 > address23 > phone23

 6 and 7 are connected by ip21
 7 and 8 are connected by email22


WANT ( There are two non-connected clusters )
==============================================

CLUSTER                    UNIQUE CONNECTED CLUSTERS (ie ip2 only occurs once)

 1     za1>email1>ip1>address1>phone1>za2>email2>ip2>phone2>za3>email3>
       address2>phone5>za4>email5>address3>phone13>za5>ip13>address13

 2     za11>email21>ip21>address21>phone21>za12>email22>address22>phone22>za13>ip22>address23>phone23

WORKING CODE
============

   R - all other code is prep for input and output

        cl <- clusters(graph.data.frame(combspl))$membership[-(1:length(spl))];

    igraph package is heavily used and debugged (not true of all R packages)

FULL SOLUTION

*                _                  _       _
 _ __ ___   __ _| | _____        __| | __ _| |_ __ _
| '_ ` _ \ / _` | |/ / _ \_____ / _` |/ _` | __/ _` |
| | | | | | (_| |   <  __/_____| (_| | (_| | || (_| |
|_| |_| |_|\__,_|_|\_\___|      \__,_|\__,_|\__\__,_|

;

options validvarname=upcase;
libname sd1 "d:/sd1";
data sd1.have(keep=str);
input (Application_ID Email_ID IP_ID Address_ID phone_ID) ( :$20.);
array chr _character_;
str=catx('>',of _character_);
cards4;
za1 email1 ip1 address1 phone1
za2 email2 ip2 address1 phone2
za3 email3 ip2 address2 phone5
za4 email5 ip1 address3 phone13
za5 email1 ip13 address13 phone13
za11 email21 ip21 address21 phone21
za12 email22 ip21 address22 phone22
za13 email22 ip22 address23 phone23
;;;;
run;quit;


%utl_submit_wps64('
libname sd1 "d:/sd1";
options set=R_HOME "C:/Program Files/R/R-3.3.2";
libname wrk "%sysfunc(pathname(work))";
proc r;
submit;
source("c:/Program Files/R/R-3.3.2/etc/Rprofile.site",echo=T);
library(igraph);
library(haven);
data <-read_sas("d:/sd1/have.sas7bdat");
data<-as.character(data$STR);
spl <- strsplit(data,">");
combspl <- data.frame(
  grp = rep(seq_along(spl),lengths(spl)),
  val = unlist(spl)
);
cl <- clusters(graph.data.frame(combspl))$membership[-(1:length(spl))];
dat <- data.frame(cl);
dat[,2] <- row.names(dat);
a <- character(0);
for (i in 1:max(cl)) {
  a[i] <- paste(paste0(dat[(dat[,1] == i),][,2]), collapse=">");
};
endsubmit;
import r=a data=wrk.linkages;
run;quit;
');

proc print data=linkages width=min;
run;quit;

Up to 40 obs from linkages total obs=2

CLUSTERS

 1     za1 > email1 > ip1 > address1 > phone1 > za2 > email2 > ip2 > phone2 >
       za3 > email3 > address2 > phone5 > za4 > email5 > address3 > phone13 >
       za5 > ip13 > address13

 2     za11 > email21 > ip21 > address21 > phone21 > za12 > email22 >
       address22 > phone22 > za13 > ip22 > address23 > phone23